C++14(g++5.4) 解法, 执行用时: 16ms, 内存消耗: 9976K, 提交时间: 2019-03-30 20:48:22

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 10005, maxm = 105, inf = 1000000000, p = 1000000007;
ll c[maxn][maxm], f[20][maxn];
int main()
{
    ll n, k, D;
    cin >> n >> k >> D;
    for(int i = 0; i <= n; i++)
    {
        c[i][0] = 1;
        for(int j = 1; j <= i && j <= k; j++)
        {
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % p;
        }
    }
    f[0][0] = 1;
    for(ll i = 0; i <= 16; i++)
    {
        for(ll j = 0; j <= n - k; j++)
        {
            for(ll x = 0; x * (D + 1) <= k / 2 && x * (D + 1) * (1ll << i) + j <= n - k; x++)
            {
                f[i + 1][j + x * (D + 1) * (1ll << i)] =
                (f[i + 1][j + x * (D + 1) * (1ll << i)] + f[i][j] * c[k/2][x * (D + 1)]) % p;
            }
        }
    }
     ll ans = c[n][k];
     for(int i = 0; i <= n - k; i++)
     {
         ans = (ans - f[16][i] * c[n - k - i + k / 2][k / 2] % p) % p;
     }
     cout << (ans + p) % p << endl;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 14ms, 内存消耗: 10220K, 提交时间: 2019-03-09 21:28:49

#include<stdio.h>
#include<string.h>
#define mod 1000000007
#define LL long long
LL C[10005][105], dp[18][10005], er[18] = {1};
int main(void)
{
	LL i, j, n, k, d, x, ans;
	for(i=0;i<=10000;i++)
		C[i][0] = 1;
	for(i=1;i<=15;i++)
		er[i] = er[i-1]*2;
	for(i=1;i<=10000;i++)
	{
		for(j=1;j<=100;j++)
			C[i][j] = (C[i-1][j]+C[i-1][j-1])%mod;
	}
	while(scanf("%lld%lld%lld", &n, &k, &d)!=EOF)
	{
		memset(dp, 0, sizeof(dp));
		dp[0][0] = 1;
		for(i=0;i<=15;i++)
		{
			for(j=0;j<=n-k;j++)
			{
				dp[i+1][j] = (dp[i+1][j]+dp[i][j])%mod;
				for(x=1;x*(d+1)*er[i]+j<=n-k&&x*(d+1)<=k/2;x++)				//总石子数不能超过n-m，并且第i位二进制为1的石子堆数不能超过总堆数
					dp[i+1][j+x*(d+1)*er[i]] = (dp[i+1][j+x*(d+1)*er[i]]+dp[i][j]*C[k/2][x*(d+1)]%mod)%mod;
			}
		}
		ans = 0;
		for(i=0;i<=n-k;i++)
			ans = (ans+dp[15][i]*C[n-i-k/2][k/2])%mod;
		printf("%lld\n", ((C[n][k]-ans)%mod+mod)%mod);
	}
	return 0;
}