题目描述
这个游戏是在一个1*n的棋盘上进行的,棋盘上有k个棋子,一半是黑色,一半是白色。最左边是白色棋子,最右边
是黑色棋子,相邻的棋子颜色不同。
小奇可以移动白色棋子,提比可以移动黑色的棋子,它们每次操作可以移动1到d个棋子。每当移动某一个棋子时,
这个棋子不能跨越两边的棋子,当然也不可以出界。当谁不可以操作时,谁就失败了。小奇和提比轮流操作,现在
小奇先移动,有多少种初始棋子的布局会使它有必胜策略?
输入
共一行,三个数,n,k,d。对于100%的数据,有1<=d<=k<=n<=10000, k为偶数,k<=100。
输出
输出小奇胜利的方案总数。答案对1000000007取模。
样例输入
10 4 2
样例输出
182
题解
博弈论+dp
我们去 %CQzhangyu 吧
#include <cstdio>
#include <cstring>
#define mod 1000000007
typedef long long ll;
ll c[10010][110] , f[16][10010];
int main()
{
int n , m , d , i , j , k;
ll ans = 0;
scanf("%d%d%d" , &n , &m , &d) , d ++ ;
c[0][0] = 1;
for(i = 1 ; i <= n ; i ++ )
{
c[i][0] = 1;
for(j = 1 ; j <= m ; j ++ )
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;
}
f[0][0] = 1;
for(i = 1 ; d * (1 << (i - 1)) <= n - m ; i ++ )
for(j = 0 ; j <= n - m ; j ++ )
for(k = 0 ; k * (1 << (i - 1)) <= j && k <= (m >> 1) ; k += d)
f[i][j] = (f[i][j] + f[i - 1][j - k * (1 << (i - 1))] * c[m >> 1][k]) % mod;
for(j = 0 ; j <= n - m ; j ++ ) ans = (ans + f[i - 1][j] * c[n - (m >> 1) - j][m >> 1]) % mod;
printf("%lld\n" , (c[n][m] - ans + mod) % mod);
return 0;
}