【bzoj3329】Xorequ 数位dp+矩阵乘法

题目描述

输入

第一行一个正整数，表示数据组数据，接下来T行
每行一个正整数N

输出

2*T行
第2*i-1行表示第i个数据中问题一的解，

第2*i行表示第i个数据中问题二的解，

样例输入

1
1

样例输出

1
2

题解

数位dp+矩阵乘法

$x\ xor\ 3x=2x$即$x\ xor\ 2x=3x$。而亦或的运算规则为“相同为0，不同为1”，也就是说当且仅当$a\ and\ b$不为0，即有共同的位是1时，$a\ xor\ b\neq a+b$。

所以如果$x$满足条件，则$x$与$2x$没有共同的某位为1，即要求$x$没有连续的两位为1。

那么就可以考虑dp。

设$f[i]$表示$i$位数（可能包含前导零）没有连续的两位为1的数的个数，那么$f[i]$的递推式为斐波那契数列$f[i]=f[i-1]+f[i-2]$，边界条件$f[0]=1,f[1]=2$。

第一问上一个数位dp即可。

第二问直接上矩阵乘法求斐波那契数列即可。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const ll mod = 1000000007;

struct data

{

	ll v[2][2];

	data() {memset(v , 0 , sizeof(v));}

	data operator*(const data &a)const

	{

		data ans;

		int i , j , k;

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

			for(j = 0 ; j < 2 ; j ++ )

				for(k = 0 ; k < 2 ; k ++ )

					ans.v[i][j] = (ans.v[i][j] + v[i][k] * a.v[k][j]) % mod;

		return ans;

	}

}A , ANS;

ll f[65] , g[65];

data pow(data x , ll y)

{

	data ans;

	ans.v[0][0] = ans.v[1][1] = 1;

	while(y)

	{

		if(y & 1) ans = ans * x;

		x = x * x , y >>= 1;

	}

	return ans;

}

int getp(ll n)

{

	int ans = 0;

	while(n) n >>= 1 , ans ++ ;

	return ans;

}

void init()

{

	int i;

	A.v[1][0] = A.v[0][1] = A.v[1][1] = 1;

	f[0] = 1 , f[1] = 2;

	for(i = 2 ; i <= 62 ; i ++ ) f[i] = f[i - 1] + f[i - 2];

}

ll calc(ll n , int len)

{

	if(len <= 1) return n + 1;

	else if(!(n & (1ll << (len - 1)))) return calc(n , len - 1);

	else if(n & (1ll << (len - 2))) return f[len - 1] + calc((1ll << (len - 2)) - 1 , len - 1);

	else return f[len - 1] + calc(n - (1ll << (len - 1)) , len - 1);

}

int main()

{

	init();

	int T;

	scanf("%d" , &T);

	while(T -- )

	{

		ll n;

		scanf("%lld" , &n);

		printf("%lld\n" , calc(n , getp(n)) - 1);

		printf("%lld\n" , pow(A , n + 1).v[1][1]);

	}

	return 0;

}

巴特西

【bzoj3329】Xorequ 数位dp+矩阵乘法

最新文章

热门文章