怎么SDOI2011和SDOI2019的两道题这么像啊。。(虽然并不完全一样)
题目链接: (bzoj) https://www.lydsy.com/JudgeOnline/problem.php?id=2281
(luogu) https://www.luogu.org/problemnew/show/P2490
题解: 博弈论好难啊完全学不来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). 若(age x), 则改变这(a)个中的(x)个即可；若(bge d+1-x)则可以把(b)个中的((d+1-x))个从(0)变成(1); 否则另外选择(t)堆之外的((x-a))堆变成(1), 则选的总数为((x-a)+a+b=x+ble d+1-b+b=d+1), 故移动依然合法。(怎么写着写着就变成抄别的题解了……)
然后问题转化为求(m)个数和为(n)二进制每一位(1)的个数都为((d+1))的倍数的方案数。(计数我也不会啊呜呜呜……)
设(dp[i][j])表示考虑二进制低(i)位，和为(j)的方案数，随便枚举一下转移即可
时间复杂度很低。
代码
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<iostream>
#define llong long long
using 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<<i)) {y-=(1ll<<i); ret = ret*cur%P;}
cur = cur*cur%P;
}
return ret;
}
llong comb(llong x,llong y) {return x<0||y<0||x<y ? 0ll : fact[x]*finv[y]%P*finv[x-y]%P;}
int main()
{
fact[0] = 1ll; for(int i=1; i<=N; i++) fact[i] = fact[i-1]*i%P;
finv[N] = quickpow(fact[N],P-2); for(int i=N-1; i>=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<<i)<=n && (d+1)*k<=m; k++)
{
llong tmp = cur*comb(m,(d+1)*k);
dp[i][j+(d+1)*k*(1<<i)] = (dp[i][j+(d+1)*k*(1<<i)]+tmp)%P;
}
}
}
}
llong ans = 0ll;
for(int i=0; i<=n; i++)
{
llong tmp = comb(n+m-i,m)*dp[LGN][i];
ans = (ans+tmp)%P;
}
ans = (comb(n+m+m,m+m)-ans+P)%P;
printf("%lld
",ans);
return 0;
}