盛日辉的博客
0%

蓝桥-积木画

发表于 分类于 ， ，

题目

https://www.lanqiao.cn/problems/2110/learning/

一

1
2
3
4
5
6
7
8
9
10
11
12
13
mod = 1000000007
n = int(input())
dp = [[0] * 3 for _ in range(n + 1)]
# dp[i]=第i列前[填满，上面空一个，下面空一个]
dp[1] = [1, 0, 0]
dp[2] = [2, 1, 1]
# dp[3] = [5, 2, 2]
for i in range(3, n + 1):
    dp[i][0] = (dp[i - 1][0] + dp[i - 2][0] + dp[i - 1][1] + dp[i - 1][2]) % mod
    dp[i][1] = (dp[i - 1][2] + dp[i - 2][0]) % mod
    dp[i][2] = (dp[i - 1][1] + dp[i - 2][0]) % mod

print(dp[-1][0] % mod)

这是看的一个C++题解，因为一开始有一点点没想过来。但是内存超了。发现dp[i][1]和dp[i][2]是一样的，做一点改进。

二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
mod = 1000000007
n = int(input())
dp = [[0] * 2 for _ in range(3)]
# dp[i]=第i列前[填满，空一个]
dp[1] = [1, 0]
dp[2] = [2, 1]
# dp[3] = [5, 2]
ii = 0
for i in range(3, n + 1):
    ii = i % 3
    ii_1 = ii - 1
    ii_2 = ii - 2
    dp[ii][0] = (dp[ii_1][0] + dp[ii_2][0] + dp[ii_1][1] * 2) % mod
    dp[ii][1] = (dp[ii_1][1] + dp[ii_2][0]) % mod

print(dp[ii][0] % mod)

但是，这个”请求超时，请稍后重试“。

三

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
mod = 1000000007
n = int(input())
a = [[2], [1], [1]]
mat = [[1, 2, 1],
       [0, 1, 1],
       [1, 0, 0]]


def mat_mult(A, B):
    # A:ra*ca B:ca*cb C:ra*cb
    ra, ca, cb = len(A), len(A[0]), len(B[0])
    res = [[0] * cb for _ in range(ra)]
    for i in range(ra):
        for j in range(cb):
            for k in range(ca):
                res[i][j] += (A[i][k] * B[k][j]) % mod
    return res


def mat_quick_mult(n, ma):
    tmp = [[1, 0, 0],
           [0, 1, 0],
           [0, 0, 1]]
    while n:
        if n & 1:
            tmp = mat_mult(ma, tmp)
        ma = mat_mult(ma, ma)
        n >>= 1
    return tmp


if n == 2:
    print(2)
elif n == 3:
    print(5)
elif n == 1:
    print(1)
else:
    t = mat_quick_mult(n - 2, mat)
    res = mat_mult(t, a)
    print(res[0][0]%mod)

也是看到了Python的题解用到了矩阵快速幂，所以就想着在二的基础上用矩阵快速幂进行优化，但发现计算dp[i][0] = (dp[i - 1][0] + dp[i - 2][0] + dp[i - 1][1] + dp[i - 1][2]) % mod的时候用到了前面两行两列的数据，一时没法处理。后来又发现，dp[i - 2]只用到了一个数，于是就想着把它挪到dp[i - 1]后面变成一维的。最后也竟然一次写成了矩阵快速幂。