1220：统计元音字母序列的数目（1729 分）

2019-10-06 约 525 字预计阅读 2 分钟次阅读

力扣第 157 场周赛第 4 题

题目

给你一个整数 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

相似问题：

2930：重新排列后包含指定子字符串的字符串数目（2227 分）

分析

#1

递推即可

1
2
3
4
5
6
7


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        mod = 10**9+7
        a,e,i,o,u = 1,1,1,1,1
        for _ in range(n-1):
            a,e,i,o,u = (e+i+u)%mod,(a+i)%mod,(e+o)%mod,i,(i+o)%mod
        return (a+e+i+o+u)%mod

71 ms

#2

还可以用矩阵幂优化

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


mod = 10**9+7
def mul(A,B):
    return [[sum(a*b for a,b in zip(r,c))%mod for c in zip(*B)] for r in A]
def mpow(mat, n):
    res = mat
    for i in range(n.bit_length()-2,-1,-1):
        res = mul(res,res)
        if n>>i&1:
            res = mul(res,mat)
    return res

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        f = [[1],[1],[1],[1],[1]]
        A = [[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]]
        f = mul(mpow(A,n-1),f) if n>1 else f
        return sum(a[0] for a in f)%mod

15 ms

目录

1220：统计元音字母序列的数目（1729 分）

题目

分析

#1

#2

解答