自动搬运

查看原文

来自洛谷，原作者为

	VinstaG173 Si Dieu n'existait pas, il faudrait l'inventer.

搬运于2025-08-24 21:38:17，当前版本为作者最后更新于2020-01-07 22:13:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

感觉大家的题解的dp部分挺不错的了，但是k-nim部分还是不太好。这篇题解会主要讲解k-nim。

k-nim游戏是这样的：

有$N$堆石子，每次可以从不超过$k$堆中各取一些石子，不能操作者败。

这题的转化就是将相邻的白左黑右的棋子看作一堆石子，石子个数为两颗棋子之间的空格数。这样两个人移动一颗棋子都相当于从对应的堆中取出一些石子。

k-nim的解法是这样的：

首先将各堆石子数用二进制表示。

令$r_i$表示每堆石子二进制表示的第$i$位上数字之和$\bmod (k+1)$的值。

如果有任意一个$r_i \ne 0$，先手必胜；否则先手必败。

k-nim的解法证明：

敲黑板划重点啦！

如果所有的$r_i$都为$0$，则一次操作肯定会使得某些数位上的值改变。又因为一堆石子每位上都是$0$或$1$，所以变动的绝对值不会超过$k$。因此操作结束后该位置上的$r_i$必不能为$0$。

如果有一些$r_i$不为$0$。则肯定有$r_i$堆石子的数量二进制表示该位上为$1$。此时我们只要从高到低扫每一个二进制位，选择$r_i$堆该位上为$1$的石子，再使每堆石子的个数$\mathrm{xor}$ $2^i$，此时这些堆的石子个数会变少，而$r_i$会变为$0$。

但是有一个问题：如果这样选出来的石子堆数超过了$k$怎么办？

此时我们知道：如果一个数的高位从$1$变成$0$，则其低位无论怎么变化，这个数还是变小。

于是我们每次只要尽量优先选择有高位变为$0$的数，再选择该位上为$1$的数，这样由于每个位置要选的数不到$k+1$（$r_i < k+1$）个，所以总共要选的堆数不会超过$k$堆。

又因为无法操作的状态各个$r_i$均为$0$。所以我们得到了解法。

接着的dp可以参见神仙们的题解，在此不予赘述。

Code:

#include<cstdio>
const int o=1e9+7;
int n,k,d,ans;
int frc[10007],inv[10007];
int dp[17][17007];
inline int qpw(int x,int v)
{
	int r=1;
	while(v)
	{
		(v&1)&&(r=1ll*r*x%o),x=1ll*x*x%o,v>>=1;
	}
	return r;
}
inline int C(int N,int M)
{
	return 1ll*frc[N]*inv[M]%o*inv[N-M]%o;
}
int main()
{
	scanf(" %d %d %d",&n,&k,&d);
	frc[0]=1;
	for(int i=1;i<=n;++i)
	{
		frc[i]=1ll*frc[i-1]*i%o;
	}
	inv[n]=qpw(frc[n],o-2);
	for(int i=n;i;--i)
	{
		inv[i-1]=1ll*inv[i]*i%o;
	}
	dp[0][0]=1;
	for(int i=0;i<=13;++i)
	{
		for(int j=0;j<=n-k;++j)
		{
			for(int x=0;k+(x<<i)<=n&&x<<1<=k;x+=d+1)
			{
				dp[i+1][j+(x<<i)]=(dp[i+1][j+(x<<i)]+1ll*dp[i][j]*C(k>>1,x))%o;
			}
		}
	}
	for(int i=0;i<=n-k;++i)
	{
		ans=(ans+1ll*dp[14][i]*C(n-i-(k>>1),k>>1))%o;
	}
	printf("%d\n",(C(n,k)-ans+o)%o);
	return 0;
}