P5303 [GXOI/GZOI2019]逼死强迫症

题目地址：P5303 [GXOI/GZOI2019]逼死强迫症

这里是官方题解

初步分析

从题目和数据范围很容易看出来这是一个递推 + 矩阵快速幂，那么主要问题在于递推的过程。

满足条件的答案一定是以下的形式，设 \(k = n - 1\) ，左右两边为整齐的道路，中间为长度 \(p(p \geq 3)\) 的组合块：

由 \(p\) 的奇偶性，可以得到两种不同的基本图形，即 \(1 \times 1\) 的小块在同一行（ \(p\) 是偶数）和各占一行（ \(p\) 是奇数）。

数学方法

左右均为普通的铺地板问题，可以用斐波那契数列表示，通过上下翻转可以得到两种不同的中间块方案，于是答案可以表示为：

\[F_k = 2 \sum_{p=3}^{n}\ \sum_{m=p}^{n}\ f_{k-m}\ f_{m-p+1}\]

其中 \(f\) 为斐波那契数列。

转化为母函数可得：

\[\sum_{k=0}^{\infty}\ x^n\ F_k = \frac{2x^3}{(1-x)(1-x-x^2)^2}\]

DP方法

思考如何构造方案，在 \(p = 3\) 时，有两个无法分割的排列 ：、，其余方案可以通过在中心块一
侧加入一个竖向的 \(1 \times 2\) 地砖或者两个横向的 \(1 \times 2\) 地砖组成的方形获得。答案就是上述方案的所有排列数之和。

问题转化

为了更好的求解问题，将所有方案放在一棵树上，称之为“方案树”，用 \(T\) 表示。具体而言，在树上 level \(q\) 的每个节点放入 \(q\) 个配置，这些配置可以把方案拆解为 \(q\) 块可以循环排列的结构。用这种方法，每个节点的 level 数就代表该层节点的整体重复次数。那么我们的目的就是构造这样一棵树，然后求每个节点到达根节点的距离和。

构建方案树

方案树本身的递推关系可以通过如下的方式获得：

1. 在 \(T_{k-1}\) 的 level \((q - 1)\) 的每个节点末端放一个竖向的 \(1 \times 2\) 地砖。按这样的规则把新的节点从左到右放到 \(T_n\) 的 level \(q\) 的节点上。
2. 在 \(T_{k-2}\) 的 level \((q - 1)\) 的每个节点末端放两个横向的 \(1 \times 2\) 地砖组成的方形。按这样的规则把新的节点从左到右放入 \(T_n\) 的 level \(q\) 的其余节点上。

斐波那契树

这样抽象之后，我们得到了一棵“斐波那契树”：初始 \(T_0\) 和 \(T_1\) 是两棵单点树，对于所有的 \(k(k \geq 2)\) ， \(T_k\) 的左子树是 \(T_{k-1}\) ，右子树是 \(T_{k-2}\) 。我们的问题就转化成了对于每一个 \(n\)，求 \(T_k\) 上所有节点到根节点的距离之和。

将 \(T_{k-1}\) 放入 \(T_k\) 的左子树中时， \(T_{k-1}\) 的所有节点深度加深一层，那么左子树的答案就是原本的解 \(F_{k-1}\) 与 \(T_{k-1}\) 的节点个数 \(N_{k-1}\) 之和。同理，右子树的答案就是原本的解 \(F_{k-2}\) 与 \(T_{k-2}\) 的节点个数 \(N_{k-2}\) 之和。得到 DP 方程如下：

\[N_0 = N_1 = 1, N_k = N_{k-1} +N_{k-2} + 1(k \geq 2)\]

\[F_0 = F_1 = 0, F_k = F_{k-1} + F_{k-2} + N_{k-1} +N_{k-2}(k \geq 2)\]

其对应的矩阵如下：

\[
\begin{pmatrix}
F_n & F_{n - 1} & N_n & N_{n - 1} & 1
\end{pmatrix}=
\begin{pmatrix}
F_{n - 1} & F_{n - 2} & N_{n - 1} & N_{n - 2} & 1
\end{pmatrix}
\begin{pmatrix}
1 & 1 & 0 & 0 & 0\\
1 & 0 & 0 & 0 & 0\\
1 & 0 & 1 & 1 & 0\\
1 & 0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 & 1
\end{pmatrix}
\]

把这个矩阵拿去就可以用矩阵快速幂直接得到答案了。

Further more

递推方程如果进一步化简可以得到：

\[F_0 = F_1 = 0, F_k = F_{k - 1} + F_{k - 2} + 2f_n - 2 (k \geq 2)\]

其中 \(f\) 为斐波那契数列。

同样可以用于本问题的求解。

std

这里提供两份

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 5;
const int MOD = 1e9 + 7;

struct Matrix {
    int n, m;
    long long a[MAXN][MAXN];
    Matrix(int _n, int _m) : n(_n), m(_m) {
        memset(a, 0, sizeof(a));
    }

    friend Matrix operator*(const Matrix &x, const Matrix &y) {
        Matrix ans = Matrix(x.n, y.m);
        for (int i = 0; i < ans.n; ++i) {
            for (int j = 0; j < ans.m; ++j) {
                for (int k = 0; k < x.m; ++k) {
                    ans.a[i][j] += x.a[i][k] * y.a[k][j] % MOD;
                    ans.a[i][j] %= MOD;
                }
            }
        }
        return ans;
    }
};

Matrix qpow(Matrix a, int pow) {
    Matrix ans = Matrix(a.n, a.m);
    for (int i = 0; i < ans.n; i++) {
        ans.a[i][i] = 1;
    }
    for (; pow; pow >>= 1) {
        if (pow & 1) {
            ans = ans * a;
        }
        a = a * a;
    }
    return ans;
}

int main() {
    std::ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while (T--) {
        int n;
        cin >> n;
        if (n == 1 || n == 2) {
            cout << 0 << endl;
            continue;
        }
        n--;
        Matrix f = Matrix(1, 5);
        f.a[0][2] = f.a[0][3] = f.a[0][4] = 1;
        Matrix fuck = Matrix(5, 5);
        fuck.a[0][0] = fuck.a[1][0] = fuck.a[2][0] = fuck.a[3][0] = 1;
        fuck.a[0][1] = fuck.a[2][2] = fuck.a[3][2] = fuck.a[4][2] = 1;
        fuck.a[2][3] = fuck.a[4][4] = 1;
        Matrix ans = f * qpow(fuck, n - 1);
        cout << ans.a[0][0] << endl;
    }
    return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
using namespace std;
int a[27][27], f[27][27];
int n, mod = 1000000007;

int num(int x, int y, int z) {
    return x * 9 + y * 3 + z;
}

void mul(int a[27][27], int b[27][27]) {
    int c[27][27];
    memset(c, 0, sizeof(c));
    for (int i = 0; i < 27; i++)
        for (int j = 0; j < 27; j++)
            for (int k = 0; k < 27; k++)
                c[i][j] = (c[i][j] + (long long)a[i][k] * b[k][j]) % mod;
    memcpy(a, c, sizeof(c));
}

int main() {
    for (int z = 0; z < 3; z++) {
        a[num(0, 0, z)][num(0, 0, z)] = 1;
        a[num(0, 0, z)][num(1, 1, z)] = 1;
        if (z < 2) a[num(0, 0, z)][num(1, 2, z + 1)] = 1;
        if (z < 2) a[num(0, 0, z)][num(2, 1, z + 1)] = 1;

        a[num(0, 1, z)][num(1, 0, z)] = 1;
        if (z < 2) a[num(0, 1, z)][num(2, 0, z + 1)] = 1;

        a[num(0, 2, z)][num(0, 0, z)] = 1;
        a[num(0, 2, z)][num(1, 1, z)] = 1;
        if (z < 2) a[num(0, 2, z)][num(2, 1, z + 1)] = 1;

        a[num(1, 0, z)][num(0, 1, z)] = 1;
        if (z < 2) a[num(1, 0, z)][num(0, 2, z + 1)] = 1;

        a[num(1, 1, z)][num(0, 0, z)] = 1;

        a[num(1, 2, z)][num(0, 1, z)] = 1;

        a[num(2, 0, z)][num(0, 0, z)] = 1;
        a[num(2, 0, z)][num(1, 1, z)] = 1;
        if (z < 2) a[num(2, 0, z)][num(1, 2, z + 1)] = 1;

        a[num(2, 1, z)][num(1, 0, z)] = 1;
    }
    f[0][num(0, 0, 0)] = 1;

    cin >> n;
    for (; n; n >>= 1) {
        if (n & 1) mul(f, a);
        mul(a, a);
    }
    cout << ((f[0][num(0, 0, 2)] + f[0][num(0, 2, 2)]) % mod + f[0][num(2, 0, 2)]) % mod << endl;
}