题目地址：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 数就代表该层节点的整体重复次数。那么我们的目的就是构造这样一棵树，然后求每个节点到达根节点的距离和。
构建方案树
方案树本身的递推关系可以通过如下的方式获得：
- 在 \(T_{k-1}\) 的 level \((q - 1)\) 的每个节点末端放一个竖向的 \(1 \times 2\) 地砖。按这样的规则把新的节点从左到右放到 \(T_n\) 的 level \(q\) 的节点上。
- 在 \(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;
}