题目链接：https://vjudge.net/problem/ZOJ-3690
题目意思： 有n个人，每个人可以从m个数中选取其中的一个数，而且如果两个相邻的数相同，则这个数大于等于k，问这样的数一共有多少种选择，结果取模。
思路：可能是算递推式子的能力还不够吧？没有推出来。这里我们我们运用划分的思想定义F[i]表示有i个人且最后一个人选的数组大于k选择数量，G[i]表示有i个人且最后一个人选的数组小于等于k的数量。
我们可以得到以下递推式子：
F[i]=(m-k)*(F[i-1]+G[i-1]),注：第i个人选择的数大于k，当然是i-1个人最后一个人选择的数大于k和最后一个人小于等于k的数量之和乘以大于k的数的数量，因为第i个人选择的是大于k的数，所以不被题目的限制条件限制。
G[i]=k*F[i-1]+(k-1)*G[i-1],注：第i个人选择的数小于等于k，当然是i-1个人最后一个人选择大于k的数量乘以k加上i-1个人最后一个人选择小于等于k，为了让相邻的选择不同，所以乘以（k-1）。
答案就是G[n]+F[n]。
算递推式子的时候，看到这种以某个数k为限制的时候，应该以k为划分去思考问题。对今后算递推式子也算有点启发吧。
代码：（有了递推式子以后代码就很简单了，套路的矩阵快速幂）
1 //Author: xiaowuga 2 #include <bits/stdc++.h> 3 #define maxx INT_MAX 4 #define minn INT_MIN 5 #define inf 0x3f3f3f3f 6 #define size 2 7 #define MOD 1000000007 8 using namespace std; 9 typedef long long ll; 10 ll a,b,c; 11 struct Matrix{ 12 ll mat[3][3]; 13 void clear(){ 14 memset(mat,0,sizeof(mat)); 15 } 16 Matrix operator * (const Matrix & m) const{ 17 Matrix tmp; 18 for(int i=0;i<size;i++) 19 for(int j=0;j<size;j++){ 20 tmp.mat[i][j]=0; 21 for(int k=0;k<size;k++){ 22 tmp.mat[i][j]+=mat[i][k]*m.mat[k][j]%MOD; 23 tmp.mat[i][j]%=MOD; 24 } 25 } 26 return tmp; 27 } 28 }; 29 Matrix POW(Matrix m,ll k){ 30 Matrix ans; 31 ans.clear(); 32 for(int i=0;i<size;i++) ans.mat[i][i]=1; 33 while(k){ 34 if(k&1) ans=ans*m; 35 k/=2; 36 m=m*m; 37 } 38 return ans; 39 } 40 int main() { 41 ios::sync_with_stdio(false);cin.tie(0); 42 while(cin>>a>>b>>c){ 43 Matrix m; 44 m.clear(); 45 m.mat[0][0]=m.mat[0][1]=b-c; 46 m.mat[1][0]=c;m.mat[1][1]=c-1; 47 Matrix ans=POW(m,a-1); 48 ll ans1=0,ans2=0; 49 ans1=((ans.mat[0][0]*(b-c))%MOD+(ans.mat[0][1]*c)%MOD)%MOD; 50 ans2=((ans.mat[1][0]*(b-c))%MOD+(ans.mat[1][1]*c)%MOD)%MOD; 51 cout<<(ans1+ans2)%MOD<<endl; 52 } 53 return 0; 54 }