BZOJ 4347 Nim z utrudnieniem

发表于 | 更新于

Link

Solution

问题就是在nn个数字a[i]a[i]中选出dd的倍数个，使得这些数字的 值为给定值，询问方案数目。 直接DP是很显然的：f[i][j][k]f[i][j][k]表示算到了第ii个数字，取的数字 值为jj，取了的个数 的方案数目。 方程为 发现卡空间，可以直接把这个方程用0101背包的方法原地转移。 发现TLE，那就把a[]a[]排个序，每次只需要处理a[i]<<1a[i]<<1个数字，总复杂度O(Md)O(Md)。 看到Claris大神给了另一个DP： 方程相应为 这样确实就需要用那种神奇的方法了……这个神奇的方法确实很厉害，应该能在别的地方用到，但我还是觉得对这道题来说我的方法好一些。

Tips

如果给定一个∑<x\sum < x的条件，要对这个条件思考一下能不能用来优化。另一个例子就是SDOI的那道虚树DP。 的题目排序之后就可以让 的值域单调，也许能有些用处。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <lucida>
using std::sort;
const int MAXN=500000+11,MAXS=1048576+11,P=1e9+7;
int main() {
	freopen("input","r",stdin);
	static int f[10][MAXS],g[MAXS],a[MAXN];
	int xr=0,m=0,n,d;
	is>>n>>d;
	for(int i=1;i<=n;++i) {
		is>>a[i];
		xr^=a[i];
		m+=a[i];
	}
	sort(a+1,a+1+n);
	f[0][0]=1;
	int lim=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];
		}
		for(int j=d-1;j>=1;--j) {
			for(int k=0;k<=lim;++k) {
				(f[j][k]+=f[j-1][k^a[i]])%=P;
			}
		}
		for(int k=0;k<=lim;++k) {
			(f[0][k]+=g[k^a[i]])%=P;
		}
	}
	int Ans=n%d?f[0][xr]:(f[0][xr]-1+P)%P;
	os<<Ans<<'\n';
	return 0;
}
//plus 另一种状态表示.