[POI2016]Nim z utrudnieniem(博弈论+dp+位运算)

\(\text{miku}\)\(\text{rin}\) 两个人玩游戏,一共有 \(m\) 颗石子,\(\text{miku}\) 把它们分成了 \(n\) 堆,每堆石子数分别为 \(a_1,a_2,...,a_n\),每轮可以选择一堆石子,取掉任意颗石子,但不能不取。谁先不能操作,谁就输了。在游戏开始前,\(\text{rin}\) 可以扔掉若干堆石子,但是必须保证扔掉的堆数是 \(d\) 的倍数,且不能扔掉所有石子

\(1\le n\le 5\times 10^5,1\le d\le 10,1\le a_i\le 10^6\)\(m\) 不直接给出,但数据保证 \(1\le m\le 10^7\)

\(\text{miku}\) 先手,请问 \(\text{rin}\) 有多少种扔的方式,使得 \(\text{rin}\) 能够获胜。

基于“ \(n\) 堆石子各自的数量的异或和为 \(0\) 则先手必败”这一人尽皆知的结论,我们发现,可以把答案从“剩下的”转化为“选取的”——设原序列异或和为 \(s\),如果选取的石子的异或和也是 \(s\),则剩下的部分一定保证先手必败。

那么,同样基于上述结论,我们考虑一个 dp。设\(f_{i,j,k}\) 表示考虑前 \(i\) 堆石子,在\(d\) 意义下,选取了 \(j\) 堆石子,其异或和为 \(k\) 的方案数。转移方程是显然的,即

\(\large{f_{i,j,k}=f_{i-1,j,k}+f_{i-1,j-1,k \oplus a_i}}\)

时空双爆炸!两者均为 \(O(n \times d \times a_{\max})\)。考虑优化。

对于空间,不难想到用滚动数组解决,压掉 \(n\) 那一维,类似背包(注意要倒着跑);对于时间,有一个巧妙的结论:\(x\) 与小于自己的数异或,其结果小于 \(x \times 2\)。所以,可以将 \(a\) 排序,每一次只跑到与 \(a_i\) 位数相同的最大数 \(u\)。这样,时间复杂度就只有 \(O(m\times d)\) 了。

下面是 AC 代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
inline int rd(){
	#define gc getchar
	int x=0,f=1;char c=gc();
	for(;!isdigit(c);c=gc()) f^=(c==‘-‘);
	for(;isdigit(c);c=gc()) x=(x<<1)+(x<<3)+(c^48);
	#undef gc
	return f?x:-x;
}
const int MOD=1e9+7;
int a[500010],f[11][1050000],g[1050000];
int main(){
	int n=rd(),d=rd(),s=0;
	for(int i=1;i<=n;++i) s^=(a[i]=rd());
	sort(a+1,a+n+1);
	int lim=1;f[0][0]=1;
	for(int i=1;i<=n;++i){
		while(lim<=a[i]) lim<<=1;
		for(int k=0;k<lim;++k)
			g[k]=(f[d-1][k^a[i]]+f[0][k])%MOD;
		for(int j=d-1;j;--j)
			for(int k=0;k<lim;++k)
				f[j][k]=(f[j-1][k^a[i]]+f[j][k])%MOD;
		for(int k=0;k<lim;++k) f[0][k]=g[k];
	}
	printf("%d\n",(f[0][s]-(n%d==0)+MOD)%MOD);
	return 0;
} 

THE END

[POI2016]Nim z utrudnieniem(博弈论+dp+位运算)

上一篇:EasyNTS 交叉编译海思系统下的可执行程序实现及测试过程


下一篇:setTimeout的第三个参数