题目

类型：动态规划
image.png

解题思路

image.png

代码

  1. class Solution {
  2.     int MOD = (int)1e9+7;
  3.     long[][] mul(long[][] a, long[][] b) {
  4.         int r = a.length, c = b[0].length, z = b.length;
  5.         long[][] ans = new long[r][c];
  6.         for (int i = 0; i < r; i++) {
  7.             for (int j = 0; j < c; j++) {
  8.                 for (int k = 0; k < z; k++) {
  9.                     ans[i][j] += a[i][k] * b[k][j];
  10.                     ans[i][j] %= MOD;
  11.                 }
  12.             }
  13.         }
  14.         return ans;
  15.     }
  16.     public int countVowelPermutation(int n) {
  17.         long[][] ans = new long[][]{
  18.             {1}, {1}, {1}, {1}, {1}
  19.         };
  20.         long[][] mat = new long[][]{
  21.             {0, 1, 0, 0, 0},
  22.             {1, 0, 1, 0, 0},
  23.             {1, 1, 0, 1, 1},
  24.             {0, 0, 1, 0, 1},
  25.             {1, 0, 0, 0, 0},
  26.         };
  27.         int x = n - 1;
  28.         while (x != 0) {
  29.             if ((x & 1) != 0) ans = mul(mat, ans);
  30.             mat = mul(mat, mat);
  31.             x >>= 1;
  32.         }
  33.         long sum = 0;
  34.         for (int i = 0; i < 5; i++) sum += ans[i][0];
  35.         return (int)(sum % MOD);
  36.     }
  37. }