洛谷P2490 [SDOI2011] 黑白棋

传送门

首先容易想到，白色棋子与其右边的黑色棋子越靠越近，最后挨在一起，与其他棋子无关。

朴素地想到 \(NimK\) 的建模，一共有 \(\dfrac{k}{2}\) 堆石子，每次取 \(d\) 堆。

注意到必胜局面比较难求，适合正难则反，用总方案数 \(\dbinom{n}{k}\) 减去必败局势。

难点在于 \(DP\)。

设计状态 \(dp_{i,j}\) 表示当前选完二进制第 \(i-1\) 位，一共选了 \(j\) 个石子。

考虑每个二进制位 \(\sum_{i=1}^n (a_i)_s = x(d+1)\) 必败，有转移方程：

\[dp_{i+1,j+2^ix(d+1)} = \sum dp_{i,j}\times \binom{\frac{k}{2}}{x(d+1)} \]

因为 \(n \le 1e4\)，\(i\) 遍历到 \(10\) 的样子就行了。

最后统计答案需要枚举每一堆的起点位置，即在原题中的白棋的位置：

\[ans = \sum_{i=0}^{n-k} dp_{11,i} \times \dbinom{n-i-\frac{k}{2}}{\frac{k}{2}} \]

\(\huge \mathscr{Code}\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e4+100,MOD = 1e9+7;
int n,m,k,d,fac[N],inv[N],dp[13][N],ans;
int qpow(int a,int b){int ans = 1;while(b){if(b&1) ans = ans*a%MOD;a = a*a%MOD;b >>= 1; }return ans;
}
void init(int n){fac[0] = inv[0] = 1;for(int i=1;i<=n;i++) fac[i] = fac[i-1]*i%MOD;inv[n] = qpow(fac[n],MOD-2);for(int i=n-1;i;i--) inv[i] = inv[i+1]*(i+1)%MOD;
}
int Choose(int n,int m){return fac[n]*inv[m]%MOD*inv[n-m]%MOD;
}
signed main(){cin>>n>>k>>d;init(n);dp[0][0] = 1;for(int i=0;i<=11;i++){int now = (1<<i);for(int j=0;j<=n-k;j++){for(int x=0;x*(d+1)<=k/2;x++){if(j+now*x*(d+1)>n-k) break;dp[i+1][j+now*x*(d+1)] = (dp[i+1][j+now*x*(d+1)] + dp[i][j]*Choose(k/2,x*(d+1))%MOD)%MOD;}}}for(int i=0;i<=n-k;i++){ans = (ans + dp[12][i]*Choose(n-i-k/2,k/2)%MOD)%MOD;}ans = (Choose(n,k)-ans+MOD)%MOD;cout<<ans;return 0;
}