自动搬运

查看原文

来自洛谷，原作者为

	Ebola 来证个定理吧！

搬运于2025-08-24 22:09:59，当前版本为作者最后更新于2019-06-29 09:16:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

我的做法似乎和楼上几位大佬的完全不同，大佬们的做法都可以NTT优化，我的做法就只能过这个题的数据范围了qwq

这题转化成阶梯nim问题是很显然的，移动一枚金币，就是把下一堆石子拿若干个放到前一堆。先手必胜当且仅当编号为奇数的堆石子数异或和非零

阶梯nim结论的证明

假设两人都移动奇数堆的石子

对于一个先手必胜局面，先手肯定优先移动奇数堆的若干个石子使得奇数堆石子异或和为$0$从而进入P状态，然后后手萎蛋

如果后手试图打破规则，移动了偶数堆的若干个石子，那先手就把他移了的那些石子再往左移一堆，那么局面不改变，后手仍处于P状态

先手必败局面也是类似的证法

普通nim游戏先手必胜方案计数的一种方法（本题解法的前置芝士）

考虑统计先手必败（P状态）的方案数。实际上就是把$n$个石子放入$m$个容器，使得所有容器的石子数异或和为$0$

首先$n$为奇数的情况显然不可能异或和为$0$，所以设$D_k(n)$表示$k$堆石子一共$2n$个的P状态方案数

$2n$个石子且每堆石子都是偶数（以下简称“偶堆”，相应的有“奇堆”）的一个P状态，可以被认为是将$n$堆石子的某个P状态中每堆石子的数量翻倍，这意味着所有P状态与所有仅包含偶堆的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}$去减一下就好了

#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;
}