JSOI2016 位运算

【题解】[JSOI2016] 位运算

题目描述：

JYY 最近在研究位运算。他发现位运算中最有趣的就是异或 (xor) 运算。对于两个数的异或运算，JYY 发现了一个结论：两个数的异或值为 $0$ 当且仅当他们相等。于是 JYY 又开始思考，对于 $N$ 个数的异或值会有什么性质呢？

JYY 想知道，如果在 $0$ 到 $R-1$ 的范围内，选出 $N$ 个不同的整数，并使得这 $N$ 个整数的异或值为 $0$，那么一共有多少种选择的方法呢？（选择的不同次序并不作重复统计，请参见样例）

JYY 是一个计算机科学家，所以他脑海里的 $R$ 非常非常大。为了能够方便的表达，如果我们将 $R$ 写成一个 $01$ 串，那么 $R$ 是由一个较短的 $01$ 串 $S$ 重复 $K$ 次得到的。比如，若 $S=101$，$K=2$，那么 $R$ 的二进制表示则为 $101101$。由于计算的结果会非常大，JYY 只需要你告诉他选择的总数对 $10^9+7$ 取模的结果即可。

对于 $100\%$ 的数据，$3 \le N \le 7$，$1 \le k \le 10^5$，$1 \le |S| \le 50$。

题目分析：

首先若异或值为 $0$ 也就是说按每一位考虑，每一位 $1$ 的个数都为偶数。
所以可以按每一位分别考虑，使用 $dp$ 解决这个问题。
因为题目要求选择的数不同，所以为了方便转移我们可以考虑使用最小表示法记录数的相同情况，也就是维护一个长度为 $7$ 的序列，其中第 $i$ 个数表示第一个与 $i$ 相同的数的位置。
直接爆搜可以发现有用状态数为 $877$ 个。
把这个东西推推就会发现，根本做不了，因为状态数太多了，所以考虑能不能优化状态。
首先我们如果用这种状态转移我们最后还要除以一个阶乘，因为一种方案的不同排列方式也被我们当作了不同方案，所以优化状态可以考虑从这个入口。
令我们的选择的数为 $x_1,x_2,x_3,\cdots,x_n$，那么我们强制令 $R > x_1 > x_2 > x_3 > \cdots > x_n$，这样我们最后的方案数就不重不漏了。
我们的状态就是仅考虑二进制下前几位的时候的情况，因为仅考虑前几位有可能出现 $x_i = x_{i+1}$ 的情况，所以不妨直接记录一个 $01$ 状态 $S$，如果 $S_i = 1$ 则意味着 $x_i = x_{i-1}$，如果 $S_i = 0$ 则意味着 $x_i < x_{i-1}$，这里默认 $x_0 = R$。
这样的话转移其实就是枚举当前这一位每一个数都是 $0$ 还是 $1$，直接暴力做的复杂度就是 $O(k \times |S| \times 2^n \times 2^n \times n)$。
但是注意到我们的 $R$ 是循环的，所以可以处理出一个循环节里 $dp[S]$ 对 $dp[T]$ 的贡献系数，然后使用矩阵快速幂就可以实现快速转移了。
而一个循环节里 $dp[S]$ 对 $dp[T]$ 的贡献并没有什么公式可以求，所以可以对于每一个 $S$ 都将 $dp[S]$ 作为 $dp$ 的初值然后跑一遍 $dp$ 就可以得到贡献系数。
时间复杂度为 $O(|S| \times 2^{3n} \times n + 2^{3n} \times \log k)$

代码：

点击查看代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9+7;
const int N = 100;
void add(int &a,int b){
	a = (a + b) % MOD;
}
struct Matrix{
	int n,m;
	int a[200][200];
	Matrix(){
		memset(a,0,sizeof(a));
	}
	void init(){
		for(int i=0; i<n; i++)	a[i][i] = 1;
	}
}; 
Matrix operator * (Matrix a,Matrix b){
	Matrix c;
	c.n = a.n,c.m = b.m;
	for(int i=0; i<c.n; i++){
		for(int j=0; j<c.m; j++){
			for(int k=0; k<a.m; k++){
				add(c.a[i][j],a.a[i][k]*b.a[k][j]);
			}
		}
	}
	return c;
}
int dp[100][200],flag[N];
char s[N];
signed main(){
//	freopen("in.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	int n,k;scanf("%lld%lld",&n,&k);
	scanf("%s",s+1);
	int len = strlen(s+1);
	Matrix tmp;
	tmp.n = tmp.m = 1<<n;
	for(int T=0; T<(1<<n); T++){
		memset(dp,0,sizeof(dp));
		dp[0][T] = 1;
		for(int i=0; i<len; i++){
			for(int S=0; S<(1<<n); S++){
//				printf("%lld ",dp[i][S]);
				if(!dp[i][S])	continue;
				for(int tmp=0; tmp<(1<<n); tmp++){
					if(__builtin_popcount(tmp) % 2 == 1)	continue;
					int res = 0,tag = 1;
					flag[0] = s[i+1] - '0';
					for(int j=1; j<=n; j++)	flag[j] = (tmp >> (j-1)) & 1;
					for(int j=1; j<=n; j++){
						if((S >> (j-1)) & 1){
							if(flag[j] && !flag[j-1])	tag = 0;
							if(flag[j] == flag[j-1])	res |= (1<<(j-1));
						}
					}
					if(!tag)	continue;
					add(dp[i+1][res],dp[i][S]);
				}
			}
//			printf("\n");
		}
		for(int S=0; S<(1<<n); S++){
			tmp.a[T][S] = dp[len][S];
		}
	}
	Matrix res;
	res.n = res.m = 1<<n;
	res.init();
	while(k){
		if(k & 1)	res = res * tmp;
		tmp = tmp * tmp;
		k >>= 1;
	}
	Matrix f;
	f.n = 1,f.m = (1<<n);
	f.a[0][(1<<n)-1] = 1;
	f = f * res;
	
	printf("%lld\n",f.a[0][0]);
	return 0;
}