怎么SDOI2011和SDOI2019的两道题这么像啊。。(虽然并不完全一样)

题目链接: (bzoj)

(luogu)

题解: 博弈论好难啊完全学不来QAQ

题目里应该有个限制，是先手不能左移，后手不能右移。

简单转化一发，就相当于有\(n\)堆石子，每次从\(1\)到\(d\)堆中取走任意多个，最后取完的人输。

其实这就是个Nim博弈套Bash博弈。

然后……然后我就不会了。

按理说……\(d=1\)的时候异或和为\(0\), 也就是每个二进制位\(1\)的个数为偶数，那么这个不是连猜都能猜出来每个二进制位\(1\)的个数为\((d+1)\)的倍数吗……Nim博弈套Bash博弈啊……

然后感性理解一下(可能也能算个证明吧): 考虑\(d=1\) Nim游戏的正确性，显然异或和为\(0\)时先手能且仅能将其变为不为\(0\)，而后手在这之后能将其变为为\(0\). 假设先手动的最高位为\(i\), 则后手动第\(i\)位上为\(1\)的另一个石子，下面的变成与之对应的即可。归纳可证。那么考虑\(d>1\), 当所有数出现次数均为\((d+1)\)的倍数时，先手不可能依然变为出现次数均为\((d+1)\)的倍数；从高到低考虑位\(j\), 设现在已经改变的堆数为\(t\),\(t\)个数中有\(a\)个在位\(j\)上为\(1\), \(b\)个为\(0\), 并假设后手改动前这一位上\(1\)的个数模\((d+1)\)总共是\(x\). 若\(a\ge x\), 则改变这\(a\)个中的\(x\)个即可；若\(b\ge d+1-x\)则可以把\(b\)个中的\((d+1-x)\)个从\(0\)变成\(1\); 否则另外选择\(t\)堆之外的\((x-a)\)堆变成\(1\), 则选的总数为\((x-a)+a+b=x+b\le d+1-b+b=d+1\), 故移动依然合法。(怎么写着写着就变成抄别的题解了……)

然后问题转化为求\(m\)个数和为\(n\)二进制每一位\(1\)的个数都为\((d+1)\)的倍数的方案数。(计数我也不会啊呜呜呜……)

设\(dp[i][j]\)表示考虑二进制低\(i\)位，和为\(j\)的方案数，随便枚举一下转移即可

时间复杂度很低。

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define llong long longusing namespace std;inline int read(){    int x=0; bool f=1; char c=getchar();    for(;!isdigit(c);c=getchar()) if(c=='-') f=0;    for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');    if(f) return x;    return -x;}const int P = 1e9+7;const int N = 2e4;const int LGN = 14;llong fact[N+3],finv[N+3];llong dp[LGN+3][N+3];int n,m,d;llong quickpow(llong x,llong y){    llong cur = x,ret = 1ll;    for(int i=0; y; i++)    {        if(y&(1ll<
         
          =0; i--) finv[i] = finv[i+1]*(i+1)%P; scanf("%d%d%d",&n,&m,&d); n-=m; m>>=1; for(int i=0; i*(d+1)<=m && i*(d+1)<=n; i++) { dp[0][i*(d+1)] = comb(m,(d+1)*i); } for(int i=1; i<=LGN; i++) { for(int j=0; j<=n; j++) { llong cur = dp[i-1][j]; if(cur) { for(int k=0; j+(d+1)*k*(1<
          
           <=n && (d+1)*k<=m; k++) { llong tmp = cur*comb(m,(d+1)*k); dp[i][j+(d+1)*k*(1<