bzoj 4347 [POI2016]Nim z utrudnieniem DP

4347: [POI2016]Nim z utrudnieniem

Time Limit: 30 Sec Memory Limit: 64 MB
Submit: 733 Solved: 281
[Submit][Status][Discuss]

Description

A和B两个人玩游戏，一共有m颗石子，A把它们分成了n堆，每堆石子数分别为a[1],a[2],...,a[n]，每轮可以选择一堆石子，取掉任意颗石子，但不能不取。谁先不能操作，谁就输了。在游戏开始前，B可以扔掉若干堆石子，但是必须保证扔掉的堆数是d的倍数，且不能扔掉所有石子。A先手，请问B有多少种扔的方式，使得B能够获胜。

Input

第一行包含两个正整数n,d(1<=n<=500000,1<=d<=10)。

第二行包含n个正整数a[1],a[2],...,a[n](1<=a[i]<=1000000)。

本题中m不直接给出，但是保证m<=10000000。

Output

输出一行一个整数，即方案数对10^9+7取模的结果。

Sample Input

5 2
1 3 4 1 2

Sample Output

%%claris https://www.cnblogs.com/clrs97/p/5006924.html

 1 #include<cstring>
 2 #include<cmath>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<iostream>
 6 
 7 #define N 1050007
 8 #define P 1000000007
 9 
10 #define Wb putchar(' ')
11 #define We putchar('
')
12 #define rg register int
13 using namespace std;
14 inline int read()
15 {
16     int x=0,f=1;char ch=getchar();
17     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
18     while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
19     return x*f;
20 }
21 inline void write(int x)
22 {
23     if(x<0) putchar('-'),x=-x;
24     if (x==0) putchar(48);
25     int num=0;char c[15];
26     while(x) c[++num]=(x%10)+48,x/=10;
27     while(num) putchar(c[num--]);
28 }
29 
30 int n,D,m,p;
31 int a[N],f[10][N],g[N];
32 
33 int add(int a,int b)
34 {
35     a+=b;
36     if (a>=P) a-=P;
37     return a;
38 }
39 int main()
40 {
41     n=read(),D=read();
42     for (rg i=0;i<n;i++)
43     {
44         int x=read();
45         a[x]++;
46         if (x>m) m=x;
47     }
48     f[0][0]=p=1;
49     for (rg i=1;i<=m;i++)
50     {
51         while(p<=i)p<<=1;
52         while(a[i]--)
53         {
54             for (rg k=0;k<p;k++) g[k]=add(f[D-1][k],f[0][k^i]);
55             for (rg j=D-1;j>=1;j--)
56                 for (rg k=0;k<p;k++)
57                     if (k<=(k^i))
58                     {
59                         int x=f[j][k];
60                         f[j][k]=add(f[j-1][k],f[j][k^i]);
61                         f[j][k^i]=add(f[j-1][k^i],x);
62                     }
63             for (rg k=0;k<p;k++) f[0][k]=g[k];
64         }
65     }
66     write(add(f[0][0],P-(n%D==0)));
67 }