题目描述

这个游戏是在一个1*n的棋盘上进行的，棋盘上有k个棋子，一半是黑色，一半是白色。最左边是白色棋子，最右边

是黑色棋子，相邻的棋子颜色不同。

 

小奇可以移动白色棋子，提比可以移动黑色的棋子，它们每次操作可以移动1到d个棋子。每当移动某一个棋子时，

这个棋子不能跨越两边的棋子，当然也不可以出界。当谁不可以操作时，谁就失败了。小奇和提比轮流操作，现在

小奇先移动，有多少种初始棋子的布局会使它有必胜策略？

输入

共一行，三个数，n，k，d。对于100%的数据，有1<=d<=k<=n<=10000, k为偶数，k<=100。

输出

输出小奇胜利的方案总数。答案对1000000007取模。

样例输入

10 4 2

样例输出

182

---

题解

博弈论+dp

我们去  吧

#include 
     
      #include 
      
       #define mod 1000000007typedef 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;}