解题思路
可以把原式移项得(x)^(2x)=(3x),而(x+2x=3x),说明(x)二进制下不能有两个连续的(1)。那么第一问就是一个简单的数位(dp),第二问考虑递推按位做,设(f(i))表示最后一位为(0)的答案,(g(i))表示最后一位为(1)的答案,那么(f(i)=g(i-1)+f(i-1)),(g(i)=f(i-1)),整理一下发现(f(i)=f(i-1)+f(i-2)),就是斐波那契的形式,直接矩乘即可。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=70;
const int MOD=1e9+7;
typedef long long LL;
int a[N],len;
LL f[N][2][2],n;
bool vis[N][2][2];
LL DFS(int x,int lst,int lim){
if(vis[x][lst][lim]) return f[x][lst][lim];
vis[x][lst][lim]=1;
if(!x) return f[x][lst][lim]=1;
if(!lst && (lim || a[x])) f[x][lst][lim]=DFS(x-1,1,lim);
f[x][lst][lim]+=DFS(x-1,0,lim|(a[x]==1));
return f[x][lst][lim];
}
struct Matrix{
int a[3][3];
void clear(){
memset(a,0,sizeof(a));
}
void init(){
a[1][1]=a[2][2]=1;
}
friend Matrix operator*(const Matrix A,const Matrix B){
Matrix ret; ret.clear();
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
for(int k=1;k<=2;k++)
(ret.a[i][j]+=1ll*A.a[i][k]*B.a[k][j]%MOD)%=MOD;
return ret;
}
}mat,ans;
Matrix fast_pow(Matrix x,LL y){
Matrix ret; ret.clear(); ret.init();
for(;y;y>>=1){
if(y&1) ret=ret*x;
x=x*x;
}
return ret;
}
int main(){
int T; scanf("%d",&T);
while(T--){
memset(vis,false,sizeof(vis));
memset(f,0,sizeof(f));
scanf("%lld",&n); LL nn=n;
len=0;
while(n) a[++len]=(n&1),n>>=1;
printf("%lld
",DFS(len,0,0)-1);
// cerr<<"!!!"<<endl;
if(nn==1) puts("2");
else if(nn==2) puts("3");
else {
// cerr<<"!!!"<<endl;
ans.clear(); mat.clear();
ans.a[1][1]=2; ans.a[1][2]=3;
mat.a[1][2]=mat.a[2][2]=mat.a[2][1]=1;
ans=ans*fast_pow(mat,nn-2);
printf("%d
",ans.a[1][2]);
}
}
return 0;
}