题意：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
       
        #include
        
         #include
         
          #include
          
           #include
           
            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;}