1220. 统计元音字母序列的数目
最直观的递推方式 class Solution { public: typedef long long ll; int mod = 1e9+7; ll ans = 0,f[20010][5] = {0}; int countVowelPermutation(int N) { for(int j=0;j<5;j++) f[1][j] = 1; for(int n=1;n<=N;n++){ f[n][1] = (f[n][1]+f[n-1][0])%mod; f[n][0] = (f[n][0]+f[n-1][1])%mod; f[n][2] = (f[n][2]+f[n-1][1])%mod; f[n][2] = (f[n][2]+f[n-1][3])%mod; f[n][4] = (f[n][4]+f[n-1][3])%mod; f[n][0] = (f[n][0]+f[n-1][4])%mod; for(int i=0;i<5;i++){ if(i==2) continue; f[n][i] = (f[n][i]+f[n-1][2])%mod; } } for(int i=0;i<5;i++) ans = (ans+f[N][i])%mod; return ans; } }; 递推关系+矩阵加速 下面的变换矩阵就是最精华的地方了。 class Solution { public: typedef long long LL; int mod = 1e9+7; void matrix_mul(LL A[][5],LL B[][5]){ LL C[5][5] = {0,0,0,0}; for(int i=0;i<5;i++){ for(int j=0;j<5;j++){ for(int k=0;k<5;k++){ C[i][j] = (C[i][j]+A[i][k]*B[k][j]%mod)%mod; } } } memcpy(B,C,sizeof C); } void quick_mul(LL A[][5],int n,LL B[][5]){ while(n){ if(n&1) matrix_mul(A,B); matrix_mul(A,A); n >>= 1; } } int countVowelPermutation(int N) { LL A[5][5] = { {0,1,0,0,0}, {1,0,1,0,0}, {1,1,0,1,1}, {0,0,1,0,1}, {1,0,0,0,0} }; LL B[5][5] = { {1,0,0,0,0}, {0,1,0,0,0}, {0,0,1,0,0}, {0,0,0,1,0}, {0,0,0,0,1} }; quick_mul(A,N-1,B); LL a0[5] = {1,1,1,1,1}; LL res[5] = {0}, ans =0; for(int i=0;i<5;i++){ for(int k=0;k<5;k++){ res[i] = (res[i]+B[k][i])%mod; } } for(int i=0;i<5;i++) ans = (ans+res[i])%mod; return ans; } }; // [a,e,i,o,u] // a = e + i + u; // e = a + i; // i = e + o; // o = i; // u = i + o;