「Luogu P5343」「XR-1」分块

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$）。

Source

[Luogu]P5343

Solution

$60 \rm pts$：

考虑 动态规划 。

先预处理出所有可能的块长 $a_1 \sim a_m$（注意要去重）。

用 $f_i$ 表示长度为 $i$ 的序列的分块方案数。

初始 $f_0 = 1$ 。（长度为 $0$ 的序列一定有 $1$ 种分块方案）

状态转移方程（考虑分出来最后一块的块长为 $a_j$）：

$$\large{ f_i = \sum\limits_{j = 1}^m f_{i - 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}$，然后才能转移。

$$\large { \begin{bmatrix} f_{size - 1}\\[1ex] f_{size-2}\\[1ex] \cdots\\[1ex] f_{1}\\[1ex] f_{0}\\[1ex] \end{bmatrix} }$$

接下来构造转移矩阵。首先根据 $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$ 。

$$\large{ \begin{bmatrix} \\[1ex] 1 & 0 & \cdots & \cdots & \cdots & 0\\[1ex] 0 & 1 & 0 & \cdots & \cdots & 0\\[1ex] 0 & \cdots & 0 & 1 & 0 & 0\\[1ex] 0 & \cdots & \cdots & 0 & 1 & 0\\[1ex] \end{bmatrix} \times\begin{bmatrix} f_{i-1}\\[1ex] f_{i-2}\\[1ex] \cdots\\[1ex] f_{i-size + 1}\\[1ex] f_{i-size}\\[1ex] \end{bmatrix}=\begin{bmatrix} f_i\\[1ex] f_{i-1}\\[1ex] \cdots\\[1ex] f_{i-size + 2}\\[1ex] f_{i-size + 1}\\[1ex] \end{bmatrix} }$$

最后是答案矩阵。

$$\large{ \begin{bmatrix} \\[1ex] 1 & 0 & \cdots & \cdots & \cdots & 0\\[1ex] 0 & 1 & 0 & \cdots & \cdots & 0\\[1ex] 0 & \cdots & 0 & 1 & 0 & 0\\[1ex] 0 & \cdots & \cdots & 0 & 1 & 0\\[1ex] \end{bmatrix}^{n-size + 1} \times\begin{bmatrix} f_{size - 1}\\[1ex] f_{size-2}\\[1ex] \cdots\\[1ex] f_{1}\\[1ex] f_{0}\\[1ex] \end{bmatrix}=\begin{bmatrix} f_n\\[1ex] f_{n-1}\\[1ex] \cdots\\[1ex] f_{n-size + 2}\\[1ex] f_{n-size + 1}\\[1ex] \end{bmatrix} }$$

答案矩阵的第 $1$ 行第 $1$ 列即是最终答案。时间复杂度为 $O(size^3\log n)$ 。

Code

#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;
}