bzoj2281 [Sdoi2011]黑白棋

一眼$nimk$游戏，后来觉得不对劲，看了黄学长博客发现真的不是$nimk$。

就当是$nimk$做吧，那么我们要保证每一位上一的个数都是$d+1$的倍数。

$dp$：$f[i][j]$表示从低到高第$i$位，前i位用了$j$个石子，必败的方案数

最后一个挡板法统计答案即可。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#define N 10050
#define mod 1000000007
#define int long long
using namespace std;
int C[N][108],bit[20],n,K,d;
int f[20][N],ans;
signed main(){
    scanf("%lld%lld%lld",&n,&K,&d);
    bit[0]=1;
    for(int i=1;i<=16;i++)bit[i]=bit[i-1]<<1;
    for(int i=0;i<=10005;i++){
        C[i][0]=1;
        for(int j=1;j<=min(i,105ll);j++)
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    }
    f[0][0]=1;
    for(int i=0;i<15;i++){
        for(int j=0;j<=n-K;j++){
            for(int k=0;k*(d+1)<=K/2&&j+k*(d+1)*bit[i]<=n-K;k++){
                (f[i+1][j+k*(d+1)*bit[i]]+=f[i][j]*C[K/2][k*(d+1)]%mod)%=mod;
            }
        }
    }
    ans=C[n][K];
    for(int i=0;i<=n-K;i++)ans=(ans-f[15][i]*C[n-i-K+K/2][K/2]%mod+mod)%mod;
    printf("%lld
",ans);
    return 0;
}