Description

小 A 和小 B 又想到了一个新的游戏.

这个游戏是在一个 \(1 \times n\) 的棋盘上进行的, 棋盘上有 \(k\) 个棋子, 一半是黑色, 一半是白色.

最左边是白色棋子, 最右边是黑色棋子, 相邻的棋子颜色不同.

小 A 可以移动白色棋子, 小 B 可以移动黑色的棋子, 他们每次操作可以移动 \(1\) 到 \(d\) 个棋子.

每当移动某一个棋子时, 这个棋子不能跨越两边的棋子, 当然也不可以出界. 当谁不可以操作时, 谁就失败了.

小 A 和小 B 轮流操作, 现在小 A 先移动, 有多少种初始棋子的布局会使他胜利呢?

Input

共一行, 三个数,\(n, k, d\).

Output

输出小 A 胜利的方案总数. 答案对 \(10^9+7\) 取模.

Sample Input

10 4 2

Sample Output

182

Data Range

对于所有的数据, 满足:\(1 \leq d \leq k \leq n \leq 10000, 2 | k, k \leq 100\)

Explanation

题解传送门:http://hzwer.com/5760.html

题解传送门:http://blog.csdn.net/weixinding/article/details/7321139

\(k = 2\) 的情况, 显然是 A 胜利

A 第一步将其棋子紧靠 B, 则接下来 B 只能右移, 若 B 移动, A 下一步也能靠着它, 除非 A 一开始就无法移动

这样答案显然是 \(C_n^2 - (n - 1)\)

其实从 \(k = 2\) 的情况我们可以看出, B 的右移是没有意义的

因为 A 可以模仿 B, 同理 A 的左移是没有意义的, 那么就能转换为一个 nim 游戏

第 \(i\) 个白子, 匹配第 \(i\) 个黑子, 把他们中间的格子看成石子堆, 变成一个每次可以取 \(d\) 堆的 nim 游戏

结论: 必败态是把每堆石子转换为二进制后, 其中每一位上为 1 的石子堆数都能被 \((d + 1)\) 整除

用 \(f[i][j]\) 表示考虑二进制前 \(i\) 位, 放置了 \(j\) 个石头的方案数, 枚举每一位

有 \(q(d+1)\) 堆是 \(1\), 即放了 \(q(d+1) \cdot 2^i\) 个, 用排列组合计算这 \(q(d+1)\) 堆是 \(k\) 堆中的那些

\[f[i+1][j+k(d+1) \cdot 2^i] += f[i][j] \cdot C_{\frac{K}{2}}^{k(d+1)}\]

然后用总方案-必败局面数, 总方案显然是 \(C_n^k\)

2015-11-22

其实转成 nim 游戏是有误的

这个游戏往左移, 是可以加石子的, 虽然后手可以模仿, 但是要消耗下次可操作的堆数, 并非没有意义

反例: d=2

[] OX [] O [] XO [] XO [] X 0 1 1 1

前两个白棋往两边移动

O [] X [] [] OXO [] XO [] X 1 0 1 1

必败能转移成必败!

所以题目中要增加限制: 先手不能左移, 后手不能右移

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

#define pow2(__x) (1<<(__x))
#define safe_add(__x,__y) __x=(((__x)+(__y))%modr)
using namespace std;
typedef long long lli;
const int maxn = 10010;
const lli modr = 1000000007ll;

lli n, K, d;
lli C_ar[maxn][210], dp[30][maxn];

lli C(int n, int m)
{
    m = min(m, n - m);
    return C_ar[n][m];
}

int main(int argc, char** argv)
{
    scanf("%lld%lld%lld", &n, &K, &d);
    K /= 2; // This looks better than an even number
    // Generating combinatory numbers using Yang Hui triangle
    for (int i = 0; i <= n; i++)
        C_ar[i][0] = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= min(2*K, (lli)i); j++)
            C_ar[i][j] = (C_ar[i-1][j] + C_ar[i-1][j-1]) % modr;
    // Working
    dp[0][0] = 1;
    for (int i = 0; i < 15; i++)
        for (int j = 0; j <= n - 2*K; j++)
            for (int k = 0; k*(d+1)<=K && j+k*(d+1)*pow2(i)<=n-2*K; k++)
                safe_add(dp[i+1][j+k*(d+1)*pow2(i)], dp[i][j]*C(K,k*(d+1)));
    lli tmp = 0;
    for (int i = 0; i <= n-2*K; i++)
        safe_add(tmp, dp[15][i]*C(n-i-K, K));
    lli sum = C(n, K*2);
    lli res = (sum - tmp + modr) % modr;
    printf("%lld\n", res);
    return 0;
}