Description
HH and LL always play games together, however, LL won every time~~.That make HH very unhappy, so this time HH is designing a new game for beating LL. Here comes the rule of the game: 1)there are exactly K piles of stones on the big table. 2)the two players play in turn. 3)on each round, the player choose a pile with fewest number of stones, and remove some stones from that pile(one to the whole pile). 4)the one who take the last stone win. Now HH has N stones in hand. In order to play the game, he is going to distribute all the N stones into K piles. For the sake of fairness, he lets LL play first. As is known to all, HH and LL are both clever boys. So they play optimally in the game. Here comes the question, HH wants to know how many different ways he can distribute the stones so that he can win the game. Assumed that the answer is X, tell him the number equal to X modulo M. NOTE: two way of distributions are considered the same if they are exactly the same after sorting in ascendant order. (i.e. 1, 3, 4, 4 and 4, 1, 3, 4 are the same, while 1, 2, 2 and 1, 2 are not).
Input
The input contains several test cases, each line representing one case. Each line contains three integer N, K, M (1 <= N <= 200, 1 <= K <= N, 1 <= M <= 1000,000,000)
Output
For each case output a line containing the answer described above.
Sample Input
2 1 100
6 2 100
Sample Output
0
1
n个石头分成k堆，两个人取石头，规则是每次只能在最少的堆里取，可以取任意的数量，求先手必败的方案数
博弈的关键在于有多少个只有1个石头的堆，奇数个且还有其他非1的堆或者是偶数个1的堆的时候先手必败。
那么前者相当于组合数学中的n个相同球放到m个相同盒子的方案数。可以通过三维dp预处理出来。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<functional>
using namespace std;
typedef unsigned long long ull;
typedef long long LL;
const int maxn = 2e2 + 10;
int T, n, m, mod;
int f[maxn][maxn][maxn], sum[maxn][maxn][maxn];
void init()
{
memset(sum, 0, sizeof(sum));
for (int i = 1; i <= n; i++)
{
f[i][1][i] = f[i][i][1] = 1;
sum[i][1][i] = sum[i][i][1] = 1;
for (int j = 2; j < i; j++)
{
for (int k = 1; k <= i - j + 1; k++)
{
f[i][j][k] = sum[i - k][j - 1][min(k, i - k - j + 2)];
sum[i][j][k] = (sum[i][j][k - 1] + f[i][j][k]) % mod;
}
}
}
}
int C(int x, int y)
{
if (x - y + 1 >= 0) return sum[x][y][x - y + 1];
return 0;
}
int main()
{
while (scanf("%d%d%d", &n, &m, &mod) != EOF)
{
if (n == m&&n % 2 == 0) { printf("%d\n", 1 % mod); continue; }
init();
int ans = 0;
for (int i = 1; i <= m; i += 2)
{
(ans += C(n - m, m - i)) %= mod;
}
printf("%d\n", ans);
}
return 0;
}