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的堆的時候先手必敗。
#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;
}