题意：N个人排成一队，每个人从1 ~ m 中选择一个数，如果相邻的俩个人选择同一个数，则这个数必须大于K， 问总共有多少种选择方式
分析：注意到n的大小，就算0（n） 的算法，都可能超时。。选不考虑这个问题，，，首先应该注意到的是，第n个人对数的选择只与第n - 1个人有关，所以
针对状态转移方程下手 我们用f[n][0] 表示长度为n， 最后一个数字小于等于k 的方案数， f[n][1] 表示长度为n ，最后一个数字大于k 的方案数
状态转移方程如下：
f[n][0] = f[n - 1][0] * ( k - 1) + f[n - 1][1] * k;
f[n][1] = f[n - 1][0] * ( m - k) + f[n - 1][1] * (m - k);
得到了这个还不够，按刚才所说，就算0(n) 的算法也解决不了，不过这种递推式可以通过构造矩阵加速
代码：
zoj3690 #include<iostream> #include<algorithm> #include<string.h> #include<stdio.h> #include<stdlib.h>using namespace std;const int N = 2; const int MOD = 1000000007;long long init[N][N], ret[N][N];void matmul(long long a[][N], long long b[][N]) {long long temp[N][N] = {0};for(int i = 0; i < N; ++i)for(int k = 0; k < N; ++k)if(a[i][k])for(int j = 0; j < N; ++j)if(b[k][j]){temp[i][j] = (temp[i][j] + a[i][k] * b[k][j]) % MOD;}memcpy(a, temp, sizeof(temp)); }void q_mod(int k) {for(int i = 0; i < N; ++i)for(int j = 0; j < N; ++j)ret[i][j] = (i == j);while(k){if(k & 1) matmul(ret, init);matmul(init, init);k >>= 1;} }int main() {int n, m, k;while(scanf("%d %d %d",&n, &m, &k) == 3){init[0][0] = m - k;init[0][1] = m - k;init[1][0] = k;init[1][1] = max(k - 1, 0);q_mod(n - 1);long long ans = ret[0][0] * (m - k) + ret[0][1] * k;ans %= MOD;ans += ret[1][0] * (m - k) + ret[1][1] * k;printf("%lld\n",ans % MOD);}return 0; }
