第十八届同济大学程序设计竞赛暨高校网络友谊赛C-困难的数学题
题目链接
问题可以抽象为在一个由n根棍子摆成的序列中插入若干个隔板，要求每个隔板间的棍子数量大于k，问有多少种放隔板的方法。
设dp[x]为共有x根棍子时放隔板的方法。如果插入了隔板，第一块隔板的左边至少要有k个木棍，也可以有k+1、k+2…根，但是要保证它的右边的木棍数不少于k，也就是左边最多有n-k根木棍。
当第一根木棍左边有k、k+1、k+2…根木棍时，剩下的木棍的摆法分别为dp[x-k]、dp[x-k-1]、dp[x-k-2]…所以有
dp[x]=i=k∑x−kdp[x−i]
这么写可以求出正确答案，但是复杂度高得离谱（O(n!)）。
注意到
dp[x−1]=i=k∑x−1−kdp[x−i]
将它与上面写出的dp[x]表达式做差，可以得到
dp[x]−dp[x−1]=dp[x−k]
即
dp[x]=dp[x−1]+dp[x−k]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
const long long mod = 1e9 + 7;
long long dp[1000005];
int k;
long long dps(int x)
{
if (x < k)
return 0;
if (dp[x])
return dp[x];
return dp[x] = (dps(x - 1) + dps(x - k)) % mod;
}
int main()
{
int x;
scanf("%d%d", &x, &k);
dp[k] = 1;
printf("%lld", dps(x));
return 0;
}
|