Counting the number of vowel sequences: “linear DP” & “Matrix quick powers”

Topic describes

This is LeetCode 1220. Count the number of vowel sequences, difficulty is difficult.

Tag: “Linear DP”, “Matrix fast Powers”

Given an integer n, please count how many strings of length n we can form according to the following rules:

Every character in a string should be a lowercase vowel (‘a’, ‘e’, ‘I ‘,’ O ‘, ‘u’)

• Each vowel'a'All I can do is follow'e'
• Each vowel'e'Followed only by'a'Or is it'i'
• Each vowel'i'You can’t have another one behind you'i'
• Each vowel'o'Followed only by'i'Or is it'u'
• Each vowel'u'Followed only by'a'

Since the answer may be large, return the result after module 109+710^9 + 7109+7.

Example 1:

Input: n = 1 Output: 5 Description: All possible strings are: "A "," E ", "I "," O ", and "u".Copy the code

Example 2:

Input: n = 2 output: 10: all possible strings are: "ae", "ea", "ei" and "ia" and "ie", "IO", "iu", "oi", "ou" and "ua".Copy the code

Example 3:

Input: n = 5 Output: 68Copy the code

Tip:

• 
  $1 <= n <= 2 * 10^4$

Linear DP

define
$f[i][j]$To consider the length is
$i + 1$String, and the ending element is
$j$Number of schemes (where
$j$On behalf of the array['a', 'e', 'i', 'o', 'u']The subscript).

Without loss of generality consider f[I][j]f[I][j]f[I][j] how to calculate.

We can start with the rules given by the problem, from
$f[i]$Go forward update
$f[i + 1]$, can also be directly used to reverse analysis symmetry.

F [I]f[I]f[I]f[I +1]f[I +1]f[I +1] is the main analysis method.

It is easy to write the transfer equation according to the conditions:

• Each vowel'a'All I can do is follow'e' ：
  $f[i + 1][1] += f[i][0]$;
• Each vowel'e'Followed only by'a'Or is it'i' ：
  $f[i + 1][0] += f[i][1]$,
  $f[i + 1][2] += f[i][1]$;
• Each vowel'i'You can’t have another one behind you'i' ：
  $F [I + 1][j] += f[I][2],$;
• Each vowel'o'Followed only by'i'Or is it'u' ：
  $f[i + 1][2] += f[i][3]$,
  $f[i + 1][4] += f[i][3]$;
• Each vowel'u'Followed only by'a' ：
  $f[i + 1][0] += f[i][4]$.

Code (use symmetry statistical scheme number code see
$P2$Thank you,@Benhao 和 @ 5 cm/s 🌸Provide, I do not understand, trying to make the difficult problem into a “whole fish feast” problem solving code 🤣) :

class Solution {
    int MOD = (int)1e9+7;
    public int countVowelPermutation(int n) {
        long[][] f = new long[n][5];
        Arrays.fill(f[0].1);
        for (int i = 0; i < n - 1; i++) {
            // Each vowel 'a' can only be followed by 'e'
            f[i + 1] [1] += f[i][0]; 
            // Each vowel 'e' can only be followed by 'a' or 'I'
            f[i + 1] [0] += f[i][1];
            f[i + 1] [2] += f[i][1];
            // Each vowel 'I' cannot be followed by another 'I'
            f[i + 1] [0] += f[i][2];
            f[i + 1] [1] += f[i][2];
            f[i + 1] [3] += f[i][2];
            f[i + 1] [4] += f[i][2];
            // Each vowel 'o' can only be followed by 'I' or 'u'
            f[i + 1] [2] += f[i][3];
            f[i + 1] [4] += f[i][3];
            // Each vowel 'u' can only be followed by 'a'
            f[i + 1] [0] += f[i][4];
            for (int j = 0; j < 5; j++) f[i + 1][j] %= MOD;
        }
        long ans = 0;
        for (int i = 0; i < 5; i++) ans += f[n - 1][i];
        return (int)(ans % MOD); }}Copy the code

class Solution {
    int MOD = (int)1e9+7;
    public int countVowelPermutation(int n) {
        long[][] f = new long[n][5];
        Arrays.fill(f[0].1);
        for (int i = 1; i < n; i++) {
            f[i][0] = f[i - 1] [1];
            f[i][1] = f[i - 1] [0] + f[i - 1] [2];
            f[i][2] = f[i - 1] [0] + f[i - 1] [1] + f[i - 1] [3] + f[i - 1] [4];
            f[i][3] = f[i - 1] [2] + f[i - 1] [4];
            f[i][4] = f[i - 1] [0];
            for (int j = 0; j < 5; j++) f[i][j] %= MOD;
        }
        long ans = 0;
        for (int i = 0; i < 5; i++) ans += f[n - 1][i];
        return (int)(ans % MOD); }}Copy the code

MOD = int(1e9) + 7
class Solution:
    def countVowelPermutation(self, n: int) -> int:
        f = [[1] * 5] + [[0] * 5 for _ in range(n - 1)]
        for i in range(1, n):
            f[i][0] = f[i-1][1]
            f[i][1] = (f[i-1][0] + f[i-1][2]) % MOD
            f[i][2] = ((((f[i-1][0] + f[i-1][1]) % MOD + f[i-1][3]) % MOD) + f[i-1][4]) % MOD
            f[i][3] = (f[i-1][2] + f[i-1][4]) % MOD
            f[i][4] = f[i-1][0]
        return (((((f[-1][0] + f[-1][1]) % MOD + f[-1][2]) % MOD + f[-1][3]) % MOD) + f[-1][4]) % MOD
Copy the code

const MOD int = 1e9 + 7
func countVowelPermutation(n int) int {
    f := make([] []int, n)
    f[0] = []int{1.1.1.1.1}
    for i := 1; i < n; i++ {
        f[i] = make([]int.5) 
        f[i][0] = f[i- 1] [1]
        f[i][1] = (f[i- 1] [0] + f[i- 1] [2]) % MOD
        f[i][2] = (((f[i- 1] [0] + f[i- 1] [1]) % MOD + f[i- 1] [3]) % MOD + f[i- 1] [4]) % MOD
        f[i][3] = (f[i- 1] [2] + f[i- 1] [4]) % MOD
        f[i][4] = f[i- 1] [0]}return ((((f[n- 1] [0] + f[n- 1] [1]) % MOD + f[n- 1] [2]) % MOD + f[n- 1] [3]) % MOD + f[n- 1] [4]) % MOD
}
Copy the code

defmodule Solution do
  @spec count_vowel_permutation(n :: integer) :: integer
  def count_vowel_permutation(n) do
    solve(n, 1.1.1.1.1)
  end
  def solve(1, a, e, i, o, u) do
    rem((a + e + i + o + u), 1000000007)
  end
  def solve(n, a, e, i, o, u) do
    solve(n - 1, add(e, i, u), add(a, i), add(e, o), i, add(i, o))
  end
  def add(n1, n2) do
    add(n1, n2, 0)
  end
  def add(n1, n2, n3) do
    rem(n1 + n2 + n3, 1000000007)
  end
end
Copy the code

-spec count_vowel_permutation(N :: integer()) -> integer(a).
count_vowel_permutation(N) ->
  solve(N, 1.1.1.1.1).

solve(1, A, E, I, O, U) ->
  (A + E + I + O + U) rem 1000000007;
solve(N, A, E, I, O, U) ->
  solve(N - 1, add(E, I, U), add(A, I), add(E, O), I, add(I, O)).
add(N1, N2) ->
  add(N1, N2, 0).
add(N1, N2, N3) ->
  (N1 + N2 + N3) rem 1000000007.
Copy the code

(define/contract (count-vowel-permutation n)
  (-> exact-integer? exact-integer?)
    (define MOD 1000000007)
    (define (ad nums [tot 0])
      (cond
        [(empty? nums) (remainder tot MOD)]
        [else (ad (cdr nums) (+ tot (car nums)))]
      )
    )
    (let loop([n n] [a 1] [e 1] [i 1] [o 1] [u 1])
      (cond
        [(= n 1) (ad (list a e i o u))]
        [else (loop (- n 1) (ad (list e i u)) (ad (list a i)) (ad (list e o)) i (ad (list i o)))]
      )
    )
    )
Copy the code

const MOD = 10 ** 9 + 7;
const add = (. nums) = > nums.reduce((a, b) = > a + b) % MOD
var countVowelPermutation = function(n,a=1,e=1,i=1,o=1,u=1) {
    return n === 1 
        ? add(a, e, i, o, u)
        : countVowelPermutation(n - 1, add(e, i, u), add(a, i), add(e, o), i, add(i, o))
};
Copy the code

const MOD = 10 ** 9 + 7;
const add = (. nums) = > nums.reduce((a, b) = > a + b) % MOD
var countVowelPermutation = function(n) {
    let [a, e, i, o, u] = [1.1.1.1.1]
    while(--n)
        ([a, e, i, o, u] = [add(e, i, u), add(a + i), add(e + o), i, add(i, o)])
    return add(a, e, i, o, u)
};
Copy the code

• Time complexity: Set CCC to the size of the character set. In this case, CCC is fixed to 555. The overall complexity is O(n∗C)O(n * C)O(n∗C)
• Space complexity: O(n∗C)O(n * C)O(n∗C)

Matrix rapid power

It is usually considered whether the recursion process can be accelerated by “matrix fast power”, mainly based on whether the recursion process is an “associative” linear recursion process.

If there is “associative” linear sequence recursion, such as “Fibonacci sequence”, can use “matrix fast power” to speed up the sequence recursion.

For students who do not know about “matrix fast powers”, you can first see “Matrix fast powers trilogy” (students who have learned the trilogy do this problem should reduce dimension) :

1. Simple problem learning “Matrix Fast Powers”
2. Simple problem learning “Matrix fast power” ⅱ
3. Application of Matrix Fast Powers: From “State Machine DP” to “Matrix Fast Powers”

We eventually needs ∑ I = 4 f \ [I] [n – 1] sum_ {I = 0} ^ {4} f [n – 1] [I] ∑ I = 4 f [I], [n – 1] will need to get part of the column into a column vector:

We also have the initial matrix (each vowel letter becomes a character independently) :

We know f [I] [X] [I] [X] f f [I] [X] dependent on [X] [I – 1] f f [X] [I – 1] f [I – 1], [X] At the same time in a “method” has been clear about the various f [I] [j] [I] [j] f f [I] [j] and [I – 1] f [X] [X] [I – 1] f f [X] [I – 1].

According to “matrix multiplication”, it is not difficult to find:

We make:

According to the recursive relationship, the following equation can be obtained:

Then according to the “associative law” of matrix multiplication, the final result can be obtained:

Code (thanks@BenhaoRow vector (row vector)

class Solution {
    int MOD = (int)1e9+7;
    long[][] mul(long[][] a, long[][] b) {
        int r = a.length, c = b[0].length, z = b.length;
        long[][] ans = new long[r][c];
        for (int i = 0; i < r; i++) {
            for (int j = 0; j < c; j++) {
                for (int k = 0; k < z; k++) { ans[i][j] += a[i][k] * b[k][j]; ans[i][j] %= MOD; }}}return ans;
    }
    public int countVowelPermutation(int n) {
        long[][] ans = new long[] [] {{1}, {1}, {1}, {1}, {1}};long[][] mat = new long[] [] {{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}};int x = n - 1;
        while(x ! =0) {
            if ((x & 1) != 0) ans = mul(mat, ans);
            mat = mul(mat, mat);
            x >>= 1;
        }
        long sum = 0;
        for (int i = 0; i < 5; i++) sum += ans[i][0];
        return (int)(sum % MOD); }}Copy the code

import numpy as np
MOD = 10 ** 9 + 7
dtype = np.dtype('uint64')
class Solution:
    def countVowelPermutation(self, n: int) -> int:
        ans, mat = np.ones(5, dtype=dtype), np.array([[0, 1, 1, 0, 1], [1, 0, 1, 0, 0], [0, 1, 0, 1, 0], [0, 0, 1, 0, 0], [0, 0, 1, 1, 0]],dtype=dtype)
        n -= 1
        while n:
            if n & 1:
                ans = ans @ mat % MOD
            mat = mat @ mat % MOD
            n >>= 1
        return int(ans.sum()) % MOD
Copy the code

const MOD int = 1e9 + 7

func countVowelPermutation(n int) (res int) {
    mul := func(X, Y [][]int)[] []int{
        res := make([] []int.len(X))
        for i := 0; i <len(res); i++{res[i] =make([]int.len(Y[0))}for i := 0; i <len(res); i++{for j := 0; j <len(res[0]); j++{for k := 0; k <len(Y); k++{ res[i][j] = (res[i][j] + X[i][k] * Y[k][j] % MOD) % MOD } } }return res
    }

    ans, mat := [][]int{{1.1.1.1.1}}, [] []int{{0.1.1.0.1}, {1.0.1.0.0}, {0.1.0.1.0}, {0.0.1.0.0}, {0.0.1.1.0}}
    n--
    for n > 0 {
        if(n & 1! =0){
            tmp := mul(ans, mat)
            ans = tmp
        }
        tmpMat := mul(mat, mat)
        mat = tmpMat
        n >>= 1
    }
    for _, row := range ans {
        for _, cell := range row{
            res = (res + cell) % MOD
        }
    }
    return
}
Copy the code

• Time complexity: a total of log⁡n\log{n}logn matrix operations need to be performed. Mat ∗matmat * matmat∗mat is the largest matrix operation, and the complexity is C3C^3C3. The overall complexity is O(log⁡n∗C3)O(\log{n} * C^3)O(logn∗C3)
• Space complexity: the upper bound of complexity is matmatmat size, and the complexity is O(C2)O(C^2)O(C2)

The last

This is the No.1220 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics on LeetCode as of the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.