题解 P5343 【【XR-1】分块】
Heartlessly
·
·
题解
Description
给定一个长度为 n\ (1 \leq n \leq 10^{18}) 的序列和 2 个 可重 集合：PR 和 NF 。现在要把它分成若干块，块的大小有限制，允许的块长为 PR \cap NF。求有多少种不同的分块方案，答案对 10^9 + 7 取模。（设最大块长为 x，1 \leq |PR|,|NF|,x \leq 100）。
Solution
考虑 **动态规划** 。
先预处理出所有可能的块长 $a_1 \sim a_m$（注意要去重）。
用 $f_i$ 表示长度为 $i$ 的序列的分块方案数。
初始 $f_0 = 1$ 。（长度为 $0$ 的序列一定有 $1$ 种分块方案）
状态转移方程（考虑分出来最后一块的块长为 $a_j$）：
直接转移是 $O(n)$ 的。
$100\rm pts$：
发现块长最大只有 $100$（$\max\limits_{i = 1}^m \{a_i\} \leq 100$），所以考虑用 **矩阵乘法** 优化上述 **DP** 。
若矩阵的大小为 $size \times size$，则有 $size = \max\limits_{i = 1}^m \{a_i\}$（因为 $f_i$ 不可能由 $f_{i - 100}$ 之前的转移过来）。
先构造初始矩阵。根据 $f_0 = 1$，**DP** 预处理出 $f_1 \sim f_{size - 1}$，然后才能转移。
接下来构造转移矩阵。首先根据 $f_i = \sum\limits_{j = 1}^m f_{i - a_j}$ 得知，矩阵第一行中，第 $a_i$ 个数为 $1$，其余为 $0$ 。剩下的 $f_{i-1} \sim f_{i - size + 1}$ 都可以在上一个矩阵中找到，所以对应的标为 $1$，其它为 $0$ 。
最后是答案矩阵。
答案矩阵的第 $1$ 行第 $1$ 列即是最终答案。时间复杂度为 $O(size^3\log n)$ 。
## Code
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
template <class T>
inline void read(T &x) {
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= c == '-';
for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
x = f ? -x : x;
}
template <class T>
inline void write(T x) {
if (x < 0) {
putchar('-');
x = -x;
}
T y = 1;
int len = 1;
for (; y <= x / 10; y *= 10) ++len;
for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}
const int MAXN = 100;
const int MOD = 1e9 + 7;
LL n;
int pr, nf, m, size, f[MAXN + 5];
bool a[MAXN + 5], b[MAXN + 5];
struct Matrix {
int mat[MAXN + 5][MAXN + 5];
inline void clear() {
memset(mat, 0, sizeof (mat));
}
inline Matrix friend operator*(Matrix a, Matrix b) {
Matrix c;
c.clear();
for (int i = 1; i <= size; ++i)
for (int j = 1; j <= size; ++j)
for (int k = 1; k <= size; ++k)
c.mat[i][j] = (c.mat[i][j] + (LL) a.mat[i][k] * b.mat[k][j]) % MOD;
return c;
}//矩阵乘法
} ans, base;
inline Matrix quickPow(Matrix x, LL p) {
Matrix res;
res.clear();
for (int i = 1; i <= size; ++i) res.mat[i][i] = 1;
for (; p; p >>= 1, x = x * x)
if (p & 1) res = res * x;
return res;
}//矩阵快速幂
int main() {
read(n), read(pr);
for (int x, i = 1; i <= pr; ++i) {
read(x);
a[x] = 1;
}
read(nf);
for (int x, i = 1; i <= nf; ++i) {
read(x);
b[x] = 1;
}//用两个桶标记允许的块长
for (int i = 1; i <= 100; ++i)
if (a[i] && b[i]) {//若同时满足 a,b
base.mat[1][i] = 1;//转移矩阵第一行
size = i;//矩阵大小
}
for (int i = 1; i < size; ++i) base.mat[i + 1][i] = 1;//转移矩阵第 2 ~ size 行
f[0] = 1;//初始状态
for (int i = 1; i < size; ++i)
for (int j = 1; j <= i; ++j)
if (a[j] && b[j])
f[i] = (f[i] + f[i - j]) % MOD;//DP 预处理 f[1] ~ f[size - 1]
for (int i = 1; i <= size; ++i) ans.mat[i][1] = f[size - i];//初始矩阵
ans = quickPow(base, n - size + 1) * ans;//得到答案矩阵
write(ans.mat[1][1]);
putchar('\n');
return 0;
}
```