标签: 动态规划
难度: Hard
给你一个整数 n，请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符串：
'a', 'e', 'i', 'o', 'u'）'a' 后面都只能跟着 'e''e' 后面只能跟着 'a' 或者是 'i''i' 后面 不能 再跟着另一个 'i''o' 后面只能跟着 'i' 或者是 'u''u' 后面只能跟着 'a'由于答案可能会很大，所以请你返回 模 10^9 + 7 之后的结果。
示例 1：
输入：n = 1 输出：5 解释：所有可能的字符串分别是："a", "e", "i" , "o" 和 "u"。
示例 2：
输入：n = 2 输出：10 解释：所有可能的字符串分别是："ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" 和 "ua"。
示例 3：
输入：n = 5 输出：68
提示：
1 <= n <= 2 * 10^4运行时间: 50 ms
内存: 16.0 MB
class Solution:
def countVowelPermutation(self, n: int) -> int:
mod=1000000007
def mult(mat1,mat2):
n=len(mat1)
m=len(mat1[0])
k=len(mat2[0])
ans=[[0]*k for _ in range(n)]
for i in range(n):
for j in range(k):
for l in range(m):
ans[i][j]=(ans[i][j]+mat1[i][l]*mat2[l][j])%(mod)
return ans
def f(mat,n,init):
ans=init
while n>0:
if n&1:
ans=mult(mat,ans)
mat=mult(mat,mat)
n=n>>1
return ans
init=[[1],[1],[1],[1],[1]]
base=[[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]]
a=f(base,n-1,init)
print(a)
ans=0
for i in range(5):
ans=(ans+a[i][0])%mod
return ans
此题解运用了矩阵快速幂的方法来解决问题。首先定义一个转移矩阵 base，其中 base[i][j] 表示从元音 i 到元音 j 的合法转移数。初始向量 init 表示每个元音字符作为起始字符的情况数。题目的主要任务是计算 base 矩阵的第 n-1 次幂与 init 向量的乘积。使用矩阵快速幂可以有效地计算矩阵的高次幂，从而减少计算时间。矩阵快速幂通过不断将幂次折半，并在每次幂次为奇数时累乘当前结果，实现了对幂次的快速计算。最后，通过遍历结果向量的元素求和并取模，得到最终的答案。
时间复杂度: O(log n)
空间复杂度: O(1)
class Solution:
def countVowelPermutation(self, n: int) -> int:
mod=1000000007
def mult(mat1,mat2):
n=len(mat1)
m=len(mat1[0])
k=len(mat2[0])
ans=[[0]*k for _ in range(n)]
for i in range(n):
for j in range(k):
for l in range(m):
ans[i][j]=(ans[i][j]+mat1[i][l]*mat2[l][j])%(mod)
return ans
def f(mat,n,init):
ans=init
while n>0:
if n&1:
ans=mult(mat,ans)
mat=mult(mat,mat)
n=n>>1
return ans
init=[[1],[1],[1],[1],[1]]
base=[[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]]
a=f(base,n-1,init)
print(a)
ans=0
for i in range(5):
ans=(ans+a[i][0])%mod
return ans
转移矩阵base的各元素值确定基于题目规定的字符串生成规则。矩阵的每行表示一个特定的元音字符，每列也对应一个元音字符。矩阵中的元素base[i][j]表示从元音i到元音j的直接转移是否合法。如果按照题目的规则，元音i可以直接跟随元音j形成合法序列，则base[i][j]为1；否则为0。例如，如果元音'a'可以跟随'b'和'e'，则矩阵中'a'行的'b'和'e'列的位置为1，其它为0。这种分布依据确保了每种元音字符转移的合法性被正确地表示在矩阵中。
矩阵快速幂是快速幂算法的一种扩展，用于高效计算矩阵的n次幂。原理是通过将幂次分解为2的幂的和，从而减少乘法次数。具体来说，每次将幂次减半，如果当前幂次为奇数，则将当前矩阵乘到结果中。这种方法通过每次减半幂次，只需要进行对数次的矩阵乘法，相比直接进行n次矩阵乘法大大提高了效率。这对于大幂次的矩阵乘法尤为重要，因为直接计算会非常耗时。
在矩阵乘法函数mult中进行mod操作是为了避免计算过程中整数溢出，并保持结果的规模可控。使用的模数`1000000007`是一个大的质数，这具有几个优点：1) 在算法竞赛和实际应用中，使用大质数可以减少可能的哈希冲突；2) 在模运算下，质数能确保乘法操作在模数范围内形成一个有良好数学性质的数环，有助于避免计算中的不必要的数值问题。
初始向量init表示每个元音字符作为起始字符的情况数，通常初始化为1。转移矩阵base表示各元音字符之间的合法转移次数。要计算长度为n的字符串总数目，我们利用矩阵快速幂计算base的n-1次幂，然后将这个结果矩阵乘以初始向量init。最终结果向量中的每个元素代表以对应元音字符结束的长度为n的字符串数目。将这些数目相加并取模，就得到了长度为n的所有可能字符串的总数目。