3329: Xorequ

题意：\(\le n \le 10^18\)和\(\le 2^n\)中满足\(x\oplus 3x = 2x\)的解的个数，第二问模1e9+7

\(x\oplus 2x = 3x\) 不就是 \(x\oplus (x<<1) = (x<<1)+x\) 吗

异或是不进位的二进制加法，那么，没有相邻的1

然后第一问数位DP就很好搞了

第二问，n个数中选i个不能相邻，\(\sum\limits \binom{n+1-i}{i}\)

太大了没法算了， DP一下试试

\(f[i][0/1]\)i个数第i个是0/1的方案数

\(f[i][0]=f[i-1][1]+f[i-1][0],\ f[i][1]=f[i-1][0]\)

矩乘就好了

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

const int N=65;

const ll P=1e9+7;

inline ll read(){

	char c=getchar();ll x=0,f=1;

	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

	return x*f;

}

int a[N], len;

ll n, f[N][2];

ll dfs(int d, int last, int sky) { //printf("dfs %d %d %d\n",d,last,sky);

	if(d==0) return 1;

	if(!sky && f[d][last]!=-1) return f[d][last];

	int lim = sky ? a[d] : 1;

	ll now=0;

	now += dfs(d-1, 0, sky && 0==lim);

	if(last!=1 && 1<=lim) now += dfs(d-1, 1, sky && 1==lim);

	return sky ? now : f[d][last]=now;

}

struct Meow{

	ll a[2][2];

	Meow(){memset(a,0,sizeof(a));}

	void ini(){a[0][0]=a[1][1]=1;}

	ll* operator [](int x) {return a[x];}

};

inline void mod(ll &x) {if(x>=P) x-=P;}

Meow operator *(Meow a, Meow b) {

	Meow c;

	for(int i=0; i<2; i++)

		for(int k=0; k<2; k++) if(a[i][k])

			for(int j=0; j<2; j++) if(b[k][j])

				mod(c[i][j] += a[i][k]*b[k][j]%P);

	return c;

}

Meow operator ^(Meow a, ll b) {

	Meow ans; ans.ini();

	for(; b; b>>=1, a=a*a)

		if(b&1) ans=ans*a;

	return ans;

}

int main() {

	freopen("in","r",stdin);

	memset(f,-1,sizeof(f));

	int T=read();

	Meow ans, f, g;

	g[0][0]=g[0][1]=g[1][0]=1; f[0][0]=f[1][0]=1;

	while(T--) {

		n=read(); len=0; ll m=n-1;

		while(n) a[++len]=n&1, n>>=1;

		printf("%lld\n", dfs(len, 0, 1)-1);

		ans=(g^m)*f;

		printf("%lld\n", (ans[0][0]+ans[1][0])%P);

	}

}

巴特西

BZOJ 3329: Xorequ [数位DP 矩阵乘法]

3329: Xorequ

最新文章

热门文章