题解 P5363 【[SDOI2019]移动金币】
Ebola
·
·
题解
我的做法似乎和楼上几位大佬的完全不同，大佬们的做法都可以NTT优化，我的做法就只能过这个题的数据范围了qwq
这题转化成阶梯nim问题是很显然的，移动一枚金币，就是把下一堆石子拿若干个放到前一堆。先手必胜当且仅当编号为奇数的堆石子数异或和非零
阶梯nim结论的证明
假设两人都移动奇数堆的石子
对于一个先手必胜局面，先手肯定优先移动奇数堆的若干个石子使得奇数堆石子异或和为0从而进入P状态，然后后手萎蛋
如果后手试图打破规则，移动了偶数堆的若干个石子，那先手就把他移了的那些石子再往左移一堆，那么局面不改变，后手仍处于P状态
先手必败局面也是类似的证法
普通nim游戏先手必胜方案计数的一种方法（本题解法的前置芝士）
考虑统计先手必败（P状态）的方案数。实际上就是把n个石子放入m个容器，使得所有容器的石子数异或和为0
首先n为奇数的情况显然不可能异或和为0，所以设D_k(n)表示k堆石子一共2n个的P状态方案数
现在考虑石子总数为$4n+2$。设奇堆的数量为$4i+2(\leq k)$，则选择奇堆的方案有$\binom{k}{4i+2}$种。我们可以在所有的奇堆中拿走一个石子，然后把所有堆的石子数减半，利用上述双射关系，对于枚举的一个$i$，就有$\binom{k}{4i+2}D_k(n-i)$种方案
所以，有：
$$D_k(2n+1)=\sum_{i=0}^{\min(n,\left\lfloor\frac{k}{4}\right\rfloor)}\binom{k}{4i+2}D_k(n-i)$$
类似地，有：
$$D_k(2n+2)=D_k(n+1)-\sum_{i=0}^{\min(n,\left\lfloor\frac{k}{4}\right\rfloor)}\binom{k}{4(i+1)}D_k(n-i)$$
利用上述式子，可以$O(nm)$求得答案，最后用总的方案数$\binom{n+m-1}{m-1}$去减一下就得到了N状态方案数
### 本题解法
还是考虑统计P状态数量
首先设$k=\left\lceil\frac{m}{2}\right\rceil$，即编号为奇数的堆数量
考虑有多少石子放入奇数堆（一定要放偶数个），多少石子放入偶数堆。放入偶数堆的可以任意，只要做个插板就行。奇数堆的就用nim游戏计数里的$D_k(n)$。于是得到：
$$cnt(P)=\sum_{i=0}^{\left\lfloor\frac{n}{2}\right\rfloor}D_k(i)\binom{n-2i+(m-k)-1}{(m-k)-1}$$
N状态的数量只要用总的数量$\binom{n+m-1}{m-1}$去减一下就好了
```cpp
#include<bits/stdc++.h>
using namespace std;
const int ha=1000000009;
const int N=150060;
int fac[N],ifac[N],d[N];
int n,m,k;
inline void add(int &x,const int &y){x=(x+y>=ha)?(x+y-ha):(x+y);}
int Pow(int a,int b)
{
int ans=1;
for(;b;b>>=1,a=1ll*a*a%ha)
if(b&1) ans=1ll*ans*a%ha;
return ans;
}
void init(int n)
{
fac[0]=1;
for(int i=1;i<=n;i++)
fac[i]=1ll*fac[i-1]*i%ha;
ifac[n]=Pow(fac[n],ha-2);
for(int i=n-1;i>=0;i--)
ifac[i]=1ll*ifac[i+1]*(i+1)%ha;
}
int C(int n,int m){return 1ll*fac[n]*ifac[m]%ha*ifac[n-m]%ha;}
int main()
{
cin>>n>>m;
init(n);
n-=m;k=(m+1)/2;
d[0]=1;
for(int i=0;i<=n/4;i++)
{
for(int j=0;j<=i&&4*j+2<=k;j++)
d[2*i+1]=(d[2*i+1]+1ll*C(k,4*j+2)*d[i-j])%ha;
d[2*i+2]=d[i+1];
for(int j=1;j<=i+1&&4*j<=k;j++)
d[2*i+2]=(d[2*i+2]+1ll*C(k,4*j)*d[i+1-j])%ha;
}
int ans=0,kk=m-k;
for(int i=0;i<=n;i++)
if(~i&1) ans=(ans+1ll*d[i/2]*C(n-i+kk,kk))%ha;
ans=(C(n+m,m)-ans+ha)%ha;
cout<<ans<<endl;
return 0;
}
```