题目描述
小A和小B又想到了一个新的游戏。
这个游戏是在一个1*n的棋盘上进行的，棋盘上有k个棋子，一半是黑色，一半是白色。
最左边是白色棋子，最右边是黑色棋子，相邻的棋子颜色不同。
小A可以移动白色棋子，小B可以移动黑色的棋子，他们每次操作可以移动1到d个棋子。
每当移动某一个棋子时，这个棋子不能跨越两边的棋子，当然也不可以出界。当谁不可以操作时，谁就失败了。
小A和小B轮流操作，现在小A先移动，有多少种初始棋子的布局会使他胜利呢？
输入输出格式
输入格式：
共一行，三个数，n,k,d。
输出格式：
输出小A胜利的方案总数。答案对1000000007取模。
输入输出样例
输入样例#1：
10 4 2
输出样例#1：
182
题解
组合数学+(nimK)游戏
以前没具体学过博弈论==
先扯一下(nimK)游戏是个啥东西:
(nimK)游戏
(nimK)游戏与(nim)游戏类似,就是给你n堆石子,最后那个不能取石子的人输,与常规(nim)游戏不同的是每个人一次可以从(K)堆中取若干棋子
必败态就是对于二进制下的每一位,所有堆石子在二进制下的该位的和能被((K+1))整除（可以类比(nim)游戏,或者也可以说成是(nim2)游戏(?)总之就是我不会证）
然后看这个题
好像题面没有给全,就是黑棋只能往左,白棋只能往右,黑白棋子必须相间
所以就可以把这(k/2)对左边是黑棋右边是白棋之间的空隙看做是每堆石子
那么就成了(nimK)游戏求先手必胜态
先手必胜不好求,考虑先手必败态再用总方案数减去先手必胜态即可
那就设(f[i][j])表示前i位已经满足条件(即所有堆石子的二进制这一位之和能被(K+1)整除)
转移就是枚举这一位放(t*(k+1))个1
dp即可
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int M = 10005 ;
const int N = 20 ;
const int mod = 1e9 + 7 ;
using namespace std ;
int n , m , k , w ;
int ans , f[N][M] , fac[M] ;
inline int Fpw(int Base , int k) {
int temp = 1 ;
while(k) {
if(k & 1) temp = 1LL * temp * Base % mod ;
Base = 1LL * Base * Base % mod ; k >>= 1 ;
}
return temp ;
}
inline int C(int n , int m) {
return 1LL * fac[n] * Fpw(fac[m] , mod - 2) % mod * Fpw(fac[n - m] , mod - 2) % mod ;
}
/*
f[i][j] 表示已经考虑了前i位,前i位的异或和都是0了,这样已经花掉了j的空间
你现在有m-1堆,每一位的二进制位必须是k的倍数
你一共能分配的点数是n-m
*/
int main() {
scanf("%d%d%d",&n,&m,&k) ;
fac[0] = 1 ; f[0][0] = 1 ; ++ k ;
for(int i = 1 ; i <= n ; i ++)
fac[i] = 1LL * fac[i - 1] * i % mod ;
for(int i = 0 ; i <= 14 ; i ++) {
for(int j = 0 ; j <= n - m ; j ++) {
if(!f[i][j]) continue ;
// 现在来枚举这一位上有几个堆去放东西
for(int t = 0 ; t <= m / 2 ; t += k) {
if(j + (1 << i) * t > n - m) break ;
f[i + 1][j + (1 << i) * t] = (f[i + 1][j + (1 << i) * t] + 1LL * f[i][j] * C(m / 2 , t) % mod) % mod ;
}
}
}
ans = C(n , m) ;
// 把一对黑白点看做一个点
for(int i = 0 ; i <= n - m ; i ++)
ans = ((ans - 1LL * f[15][i] * C( n - m / 2 - i , m / 2 ) % mod) % mod + mod) % mod ;
printf("%d
",ans) ;
return 0 ;
}