rainboy的解析

§ 解析

骨头覆盖的变种题目

核心是,怎么分类,先用脑暴 🧠,纸上画图

设f(n)f(n) 表示长度为nn的墙壁的方法数,显然有

f(n)=f(n−1)+f(n−2)+2f(n−3)+2f(n−4)+⋯+2f(0)=f(n−1)+f(n−2)+2×∑i=0n−3f(i) \begin{aligned} f(n) &= f(n-1) + f(n-2) + 2f(n-3) + 2f(n-4) +\cdots +2f(0) \\ &= f(n-1) + f(n-2) + 2\times \sum_{i=0}^{n-3}f(i) \end{aligned}

具体看代码,但是可惜,我们这个代码会,超时,因为我们的代码是二重复循环,时间为n2n^2,而n=106,n2=1012>108n = 10^6,n^2 = 10^{12} > 10^8

cpp
copy 
        
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

        #include <iostream>
using namespace std;
const int maxn = 1e6+5;

int n;
int f[maxn];

int main() {
    std::cin >> n;
    f[0] = 1;
    f[1] = 1;

    for(int i =2;i<=n;i++) {
        f[i] = f[i-1] + f[i-2];
        f[i] %= 10000;
        for(int j = i-3 ;j>=0;j--)
        {
            f[i] += 2 * f[j];
            f[i] %= 10000;
        }
        // cout << i << " " << f[i] <<endl;
    }
    cout << f[n] <<endl;
    

    return 0;
}

上面的程序超时,根据做题目的经验

  1. 要么优化代码!!!
  2. 要么优化公式.

这里优化公式,发现

f(n)=f(n−1)+f(n−2)+2f(n−3)+2f(n−4)+⋯+2f(0) \begin{aligned} f(n) &= f(n-1) + f(n-2) + \boxed{ 2f(n-3) + 2f(n-4) +\cdots +2f(0)} \\ \end{aligned}

这不就是前缀和吗!!! 😭😭😭😭😭😭😭

写代码啊!!

cpp
copy 
        
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

        #include <iostream>
using namespace std;
const int maxn = 1e6+5;

int n;
int f[maxn];
int pre_sum[maxn];

int main() {
    std::cin >> n;
    f[0] = 1;
    f[1] = 1;
    pre_sum[0] = 1;
    pre_sum[1] = 2;

    for(int i =2;i<=n;i++) {
        f[i] = f[i-1] + f[i-2];
        f[i] %= 10000;
        if( i-3 >= 0)
        {
            f[i] += 2*pre_sum[i-3];
            f[i] %= 10000;
        }
        pre_sum[i] = pre_sum[i-1] +f[i];
        pre_sum[i] %= 10000;

        // cout << i << " " << f[i] <<endl;
    }
    cout << f[n] <<endl;
    

    return 0;
}