BZOJ.3329.Xorequ(数位DP)

题目链接

x^3x=2x -> x^2x=3x
因为a^b+((a&b)<<1)=a+b，x^2x=x+2x，所以x和2x的二进制表示中不存在相邻的1。
（或者，因为x+2x=3x，所以x^2x没有抵消任何的1，所以x和2x没有相邻的1）
那么第一问数位DP，第二问上界为(2^n)，按位DP就行了。
(f[i])表示到第(i)位的方案数。每位要么填(0)要么填(1)，所以(f[i]=f[i-1]+f[i-2])。就是斐波那契数列（从斐波那契表示法也能看出与这个DP的类似）。
答案是(f[n+1])（(2^n)是(n+1)位。。==）

好像第一问能用类似二进制拆分的方法O(64)做？https://blog.csdn.net/jr_mz/article/details/50351557 。不想看了。

//824kb	16ms
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
#define mod 1000000007
typedef long long LL;
const int N=66;

int bit[N];
LL f[N][2];
bool vis[N][2];
struct Matrix
{
	int a[2][2];
	Matrix operator *(const Matrix &x)const
	{
		Matrix res;
		for(int i=0; i<2; ++i)
			for(int j=0; j<2; ++j)
			{
				LL tmp=1ll*a[i][0]*x.a[0][j]+1ll*a[i][1]*x.a[1][j];
				res.a[i][j]=tmp%mod;
			}
		return res;
	}
};

inline LL read()
{
	LL now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}
int FP(Matrix x,LL k)
{
	Matrix t=x;
	for(--k; k; k>>=1,x=x*x)
		if(k&1) t=t*x;
	return (t.a[0][0]+t.a[0][1])%mod;
	return t.a[0][0];
}
LL DFS(int x,int lim,int las)
{
	if(!x) return 1;
	if(!lim && vis[x][las]) return f[x][las];

	LL res=0; int up=lim?bit[x]:1;
	res+=DFS(x-1,lim&&!up,0);
	if(up&&!las) res+=DFS(x-1,lim&&up,1);

	if(!lim) vis[x][las]=1,f[x][las]=res;
	return res;
}
LL Solve(LL n)
{
	int cnt=0;
	for(; n; bit[++cnt]=n&1, n>>=1);
	return DFS(cnt,1,0)-1;
}

int main()
{
	Matrix mat;
	mat.a[0][0]=mat.a[0][1]=mat.a[1][0]=1, mat.a[1][1]=0;
	for(int T=read(); T--; )
	{
		LL n=read();
		printf("%lld
%d
",Solve(n),FP(mat,n));
	}
	return 0;
}