时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Ho面前有N个小球排成了一排。每个小球可以被染成M种颜色之一。
为了增强视觉效果，小Ho希望不存在连续K个或者K个以上的小球颜色一样。
你能帮小Ho计算出一共有多少种不同的染色方法么？
例如N=4, M=2, K=3，则有10种染色方法：
0010 0011 0100 0101 0110 1001 1010 1011 1100 1101
输入
三个整数：N, M和K。
对于30%的数据, 1 ≤ N, M, K ≤ 100
对于60%的数据，1 ≤ N, M, K ≤ 300
对于100%的数据，1 ≤ N, M, K ≤ 1000
输出
一个整数表示答案。注意方法数可能非常大，你只需要输出模1000000007的结果。
样例输入
4 2 3
样例输出
10
#题解：
如果只有一个小球，染色的方案是m。如果有两个小球，允许连续一次则有m(m-1)种方案，两次为m。
例：如果n=4, 颜色m=3, 连续上限k=3。m=3不变, 设方案数为e(n, m), 代表长度为n，最大连续长度恰好为m的结果
则：
n =1, e(1,1) = 3
n = 2, e(2,1)=3*2=6,e(2,2)=e(1,1)=3 (e(n,m) =e(n-1,m-1)，从e的意义上看出来,把多出来的1个小球加到一个长度为m-1的连续串里)
n = 3, e(3,1)=6*2+3*2=18, 这里可以看到e(3,1)=∑(1,k)e(2,d) * (m-1),因为对e(n-1,X)种代表的小球串染色方案，每个都可以把串拿来加长, 每个对应的方案数恰好是m-1种。至于为什么是m-1种，并不能解释，猜测是n-1, X连续的小球染色刚好可以对应一个n,1连续的小球染色。
按照分析这种染色的惯例，一般是不会把颜色作为可变变量的，因为在可变大小的区间里进行颜色分配意味着位置、颜色、连续方向都要考虑，并不是很便于编程。
考虑随着长度增加，连续上限的增加，颜色的方案数。用动态规划的方法来做。
代码：
#include <bits/stdc++.h> using namespace std; const int N = 1000; const int MOD = (int)1e9 + 7; long long dp[N + 1][N + 1]; int main() { int n, m, k; scanf("%d %d %d", &n, &m, &k); dp[1][1] = m; for (int i = 2; i <= n; ++i) { for (int j = 1; j < k; ++j) { dp[i][1] = (dp[i][1] + dp[i - 1][j] * (m - 1) % MOD) % MOD; } for (int j = 2; j < k ; ++j) { dp[i][j] = dp[i - 1][j - 1]; } } long long res = 0; for (int i = 1; i < k; ++i) { res = (res + dp[n][i]) % MOD; } #ifdef __DEBUG__ for (int i = 1; i <= n; i++) { for (int j = 1; j < k; j++) { printf("%lld ", dp[i][j]); } printf(" "); } #endif printf("%lld ", res); return 0; }
测试：
