力扣第 184 场周赛第 4 题
题目
你有一个 n x 3 的网格图 grid ，你需要用 红，黄，绿 三种颜色之一给每一个格子上色，且确保相邻格子颜色不同（也就是有相同水平边或者垂直边的格子颜色不同）。
给你网格图的行数 n 。
请你返回给 grid 涂色的方案数。由于答案可能会非常大，请你返回答案对 10^9 + 7 取余的结果。
示例 1：
输入：n = 1
输出：12
解释：总共有 12 种可行的方法：
示例 2：
输入：n = 2
输出：54
示例 3：
输入：n = 3
输出：246
示例 4：
输入：n = 7
输出：106494
示例 5：
输入：n = 5000
输出：30228214
提示：
n == grid.lengthgrid[i].length == 31 <= n <= 5000
相似问题：
分析
#1
- 按每列的颜色情况可以递推
- 相邻两列哪些情况合法可以预处理，节省时间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def numOfWays(self, n: int) -> int:
mod = 10**9+7
A = [u for u in product(range(3),repeat=3) if all(a!=b for a,b in pairwise(u))]
h = defaultdict(list)
for u in A:
h[u] = [v for v in A if all(a!=b for a,b in zip(u,v))]
f = {u:1 for u in A}
for _ in range(n-1):
g = defaultdict(int)
for u,w in f.items():
for v in h[u]:
g[v] = (g[v]+w)%mod
f = g
return sum(f.values())%mod
|
403 ms
#2
- 注意到每列的 12 种情况可以分为两类：全不相同，两边相同
- 分类后依然可以递推
1
2
3
4
5
6
7
|
class Solution:
def numOfWays(self, n: int) -> int:
mod = 10**9+7
a,b = 6,6
for _ in range(n-1):
a,b = (a*3+b*2)%mod,(a*2+b*2)%mod
return (a+b)%mod
|
7 ms
#3
这个递推式还可以用矩阵快速幂优化
解答
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 numOfWays(self, n: int) -> int:
f = [[6],[6]]
A = [[3,2],[2,2]]
f = mul(mpow(A,n-1),f) if n>1 else f
return sum(sum(A) for A in f)%mod
|
0 ms