题目连接： HDU - 5863 - cjj’s string game
设 S 为到当前长度时，所有出现过长度为 m 的子串，之后字母都相异的情况数量之和。
dp1[i] 为相同后缀长度为 i 且之前从未出现过长度为 m 的子串情况数量。
dp2[i] 为相同后缀长度为 i 且之前出现过长度为 m 的字符串的数量。
进行计数转移就行。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=1e9+7; const int N=30; ll n; int m,k; struct Matrix { ll a[N][N]; int n; Matrix(int n) : n(n) { memset(a,0,sizeof(a)); } ll * operator [] (int index) { return a[index]; } Matrix operator * (Matrix& b) { Matrix c(n); for(int i=0;i<n;++i) for(int k=0;k<n;++k) for(int j=0;j<n;++j) c[i][j]=(c[i][j]+a[i][k]*b[k][j]%mod)%mod; return c; } }; Matrix powm(Matrix a, ll b) { int n=a.n; Matrix c(n); for(int i=0;i<n;++i) for(int j=0;j<n;++j) c[i][j]=(i==j); while(b) { if(b&1) c=c*a; a=a*a; b>>=1; } return c; } int main() { ios::sync_with_stdio(false); int T; cin >> T; while(T--) { cin >> n >> m >> k; Matrix M((m+1)*2+1); for(int i=0;i<m;++i) M[0][i]=k*(k-1); for(int i=1;i<=m;++i) M[i][i-1]=k; for(int i=m+1;i<=2*m+1;++i) M[m+1][i]=k*(k-1); for(int i=m+2;i<=m*2+1;++i) M[i][i-1]=k; M[m+1][2*m+1]=k*(k-1); M[m+1][m]=k*(k-1); for(int i=m+1;i<=m*2;++i) M[i+1][i]=k; M[2*m+2][2*m+2]=k*(k-1); M[2*m+2][m-1]=k; for(int i=m+1;i<=2*m;++i) M[2*m+2][i]=k; M=powm(M,n); cout << M[2*m+2][0] << endl; } return 0; }