wy's Blog

3329: Xorequ

Description

Input

Output

Sample Input

Sample Output

HINT

Source

把题目转化一下，

即分别求出 小于等于n 和 小于等于2^n 的正整数中

满足 x xor 2x =3x 的数的个数。。。

仔细思考会发现（不要问我是怎么发现的），

满足 x xor 2x =3x 的数的个数 即 满足 二进制位中 没有两个连续的1 的数的个数。。。

对于小于等于n的，我们采取数位DP;

对于小于等于2^n的，我们用矩阵乘法（具体内容请自行YY...）

数位DP+矩阵乘法。。。

#include<cstdio>
const int Mod=1e9+7;
int a[81],len,T;
long long f[81][2],x,ans;
struct rect{
	long long o[2][2];
	rect(){
	    o[0][0]=o[0][1]=0;
	    o[1][0]=o[1][1]=0;
	}
	rect operator * (rect mul){
		rect ans;
		for (int i=0;i<2;++i)
		    for (int j=0;j<2;++j)
		        for (int k=0;k<2;++k){
		            ans.o[i][j]+=o[i][k]*mul.o[k][j];
		            ans.o[i][j]%=Mod;
				}
		return ans;
	}
	void operator *= (rect mul){
		*this = *this * mul;
	}
}P,L;
void PreTreatment(){
	f[1][0]=1; f[1][1]=1;
	for (int k=2;k<=80;++k){
		f[k][1]=f[k-1][0];
		f[k][0]=f[k-1][0]+f[k-1][1];
	}	
	P.o[0][0]=0; P.o[0][1]=1;
	P.o[1][0]=1; P.o[1][1]=1;
	L.o[0][0]=L.o[0][1]=1;
}
void Answer1(long long x){
	for (len=0;x;x/=2) a[++len]=x%2;
	ans=0;
	a[len+1]=0;
	for (int k=len;k;--k){
		for (int l=0;l<a[k];++l)
	        ans+=f[k][l];
	    if (a[k]&a[k+1]) break;
	    if (k==1) ++ans;
	}
	--ans;
	printf("%lld\n",ans);
}
rect pow(rect x,long long k){
	if (k==1) return x;
	rect tmp=pow(x,k/2);
	tmp=tmp*tmp;
	if (k%2) tmp*=x;
	return tmp;
}
void Answer2(long long x){
    rect M=pow(P,x);
    M=L*M;
	printf("%lld\n",M.o[0][1]);
}
int main(){
    PreTreatment();
    scanf("%d",&T);
    for (;T--;){
		scanf("%lld",&x);
        Answer1(x);
        Answer2(x);
	}
}