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

 #include<cstring>

 #include<cmath>

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 #define N 1050007

 #define P 1000000007

 #define Wb putchar(' ')

 #define We putchar('\n')

 #define rg register int

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}

     while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}

     return x*f;

 }

 inline void write(int x)

 {

     if(x<) putchar('-'),x=-x;

     if (x==) putchar();

     int num=;char c[];

     while(x) c[++num]=(x%)+,x/=;

     while(num) putchar(c[num--]);

 }

 int n,D,m,p;

 int a[N],f[][N],g[N];

 int add(int a,int b)

 {

     a+=b;

     if (a>=P) a-=P;

     return a;

 }

 int main()

 {

     n=read(),D=read();

     for (rg i=;i<n;i++)

     {

         int x=read();

         a[x]++;

         if (x>m) m=x;

     }

     f[][]=p=;

     for (rg i=;i<=m;i++)

     {

         while(p<=i)p<<=;

         while(a[i]--)

         {

             for (rg k=;k<p;k++) g[k]=add(f[D-][k],f[][k^i]);

             for (rg j=D-;j>=;j--)

                 for (rg k=;k<p;k++)

                     if (k<=(k^i))

                     {

                         int x=f[j][k];

                         f[j][k]=add(f[j-][k],f[j][k^i]);

                         f[j][k^i]=add(f[j-][k^i],x);

                     }

             for (rg k=;k<p;k++) f[][k]=g[k];

         }

     }

     write(add(f[][],P-(n%D==)));

 }

巴特西