
因为两人在进密室前可以商量,因此有策略保证可以必胜
#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"1.00"<<endl<<"1.00"<<endl<<"1.00"<<endl<<"1.00"<<endl;
return 0;
}


一开始没想到,但是看到斐波那契数列的时候就知道是什么意思了
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<a;++i)
#define FORD(i,a,b) for(int i=a;i>=b;--i)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define maxn int(1e5)+100
using namespace std;
int mod;
ll f[maxn];
ll a[maxn];
ll ff[maxn];
int main(){
int T;
mod=192600817;
f[1]=1;f[2]=1;
a[1]=1;a[2]=1;
ff[1]=1;ff[2]=2;
ff[0]=0;
for(int i=3;i<=maxn-100;++i){
f[i]=(f[i-1]+f[i-2])%mod;
a[i]=(f[i]*f[i])%mod;
ff[i]=(ff[i-1]+a[i])%mod;
}
while(~sc(T)){
while(T--){
int a,b,c,d;
scanf("%d%d%d%d",&a,&b,&c,&d);
int aa=a*4+b+1;
int bb=c*4+d+1;
if(bb<aa)
swap(aa,bb);
ll ans=0;
ans=(ff[bb]-ff[aa-1]+mod)%mod;
printf("%lld\n",ans);
}
}
}

对于任意的一个数,在处理一次之后肯定会转化成一个不超过600的数,因此我们可以按照题意先打表预处理前面600个鸽子数,如果k比600大就先处理一次,然后直接o(1)输出就可以了
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<a;++i)
#define FORD(i,a,b) for(int i=a;i>=b;--i)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define maxn int(1e6)+100
using namespace std;
int ans[1000];
ll work(ll x){
ll ans=0;
while(x){
ans+=(x%10)*(x%10);
x/=10;
}
return ans;
}
int an[10000000];
int main(){
int T;
vector<int> v;
mst(an,0);
for(int k=1;k<=6000;k++){
int ans=work(k);
int cnt=0;
int tot=0;
while(ans!=1){
ans=work(ans);
cnt++;
if(cnt>int(1e3))
break;
}
if(ans==1){
an[k]=1;
}
}
for(int k=1;k<=int(1e7);++k){
int aa=work(k);
if(an[aa])
v.pb(k);
}
sc(T);
while(T--){
int k;
sc(k);
cout<<v[k-1]<<endl;
}
return 0;
}

待补

十叉树深搜

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define F first
#define S second
#define maxn int(1e2)+100
#define mod 123456789
using namespace std;
int n,k,ans;
void dfs(int pre){
if(k==0)
ans=pre;
rep(i,0,9){
if(pre==0&&i==0)
continue;
if(pre*10+i<=n){
k--;
dfs(pre*10+i);
}
else
return;
}
}
int main(){
int T;sc(T);
while(T--){
sc2(n,k);
dfs(0);
printf("%d\n",ans);
}
}

公式我就不推了,是找规律做的,头很铁
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<a;++i)
#define FORD(i,a,b) for(int i=a;i>=b;--i)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define maxn int(1e5)+100
using namespace std;
int mod;
ll quick_power(ll base, ll n){
ll res = 1;
while (n > 0){
if (n & 1)
res = (res * base) % mod;
base = (base * base) % mod;
n >>= 1;
}
return res;
}
int main(){
mod=1000000007;
ll n;
while(~scanf("%lld",&n)){
printf("%lld\n",((((n-1)%mod)*quick_power(2,n)%mod)%mod+mod+1)%mod);
}
}

矩阵快速幂,几乎是模版题,可惜没时间做了

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<(a);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1
#define rson rt<<1|1
#define delf (l+r)>>1
#define lowbit(x) (x&-x)
#define pii pair<int,int>
#define F first
#define S second
#define maxn int(1e2)+100
#define mod 123456789
using namespace std;
int z[7]={0,2,1,27,37,24,6};
struct mtix{
ll a[10][10];
mtix(){mst(a,0);}
}f;
mtix mul(mtix a,mtix b){
mtix c;
for (int i=1;i<=6;i++)
for (int j=1;j<=6;j++)
for (int k=1;k<=6;k++)
{c.a[i][j]+=(a.a[i][k]*b.a[k][j])%mod;c.a[i][j]%=mod;}
return c;
}
mtix mpow(ll y){
mtix ans;
mtix tem=f;
for (int i=1;i<=6;i++)
ans.a[i][i]=1;
for (;y;tem=mul(tem,tem),y>>=1)
if (y&1) ans=mul(ans,tem);
ll sum=0;
for (int i=1;i<=6;i++)
sum+=(ans.a[1][i]*z[i])%mod;
cout<<sum%mod<<endl;
return ans;
}
int main(){
f.a[1][1]=1;f.a[1][2]=2;f.a[1][3]=1;f.a[1][4]=0;f.a[1][5]=0;f.a[1][6]=0;
f.a[2][1]=1;f.a[2][2]=0;f.a[2][3]=0;f.a[2][4]=0;f.a[2][5]=0;f.a[2][6]=0;
f.a[3][1]=0;f.a[3][2]=0;f.a[3][3]=1;f.a[3][4]=1;f.a[3][5]=0;f.a[3][6]=0;
f.a[4][1]=0;f.a[4][2]=0;f.a[4][3]=0;f.a[4][4]=1;f.a[4][5]=1;f.a[4][6]=0;
f.a[5][1]=0;f.a[5][2]=0;f.a[5][3]=0;f.a[5][4]=0;f.a[5][5]=1;f.a[5][6]=1;
f.a[6][1]=0;f.a[6][2]=0;f.a[6][3]=0;f.a[6][4]=0;f.a[6][5]=0;f.a[6][6]=1;
int T;
sc(T);
while(T--){
ll x;scanf("%lld",&x);
mpow(x-2);
}
}
