题解 P5343 【【XR-1】分块】

· · 题解

题是简单题，重在想到矩乘后怎么接着往下写。

题意不须讲了，很清楚而且很有意思。

转移方程稍微给一下，推导可以阅读别的题解。

设置状态 dp_{\ i} 指的是：长度为 i 时可行的分块方案。

我们有: （ x 指的是的可能的块长（即两人公认的其中一种块长））

dp_{\ i}= \sum dp_{\ i-x}

我们看到块总长是 \leq 1e18 的，连 N 的空间都开不下，就别提更高维的数组了。

因为开不下，所以 O(N) 递推难矣。

『递推的优化，显然矩乘。』

我们尽量少算值，整出个初始状态就差不多可以了。

要推第 i 项，要保证在所有可能的块长 x 下，第 i-x 项都已知。

因为块长不会大于 100 ，故我们可以先预处理到 dp_{\ 100} 。

开 100 * 100 的矩阵，至少可以保证递推时每一项都能推得出来。

现在就到了矩阵乘法最重要的一部分————初始化矩阵。

目前这一步的状态需要前面哪几步的状态推出？

我们通过递推式知道了，与 x 步前的状态有关系（以下的 x 指代每一种可能的块长）。

我们把 dp_{\ i} 放在原始矩阵的第 (1,1) 位置，那就把 dp_{\ i-k} 放在 (k,1) 位置。

也就是说新的矩阵的 (1,1) 位置，要由所有的 (x,1) 的总和转移而来。

那转移矩阵的第一行里必然有：对于每一个可行的 x ， (1,x) 处为 1 ，其余位置为 0 。

比如对于样例1， 1 和 2 都是可行的 x ，转移矩阵的第一行必如下图：

\begin{bmatrix}1&1&0&0&\cdots &0\end{bmatrix}

我们解决了第一行，那其他行如何处理？

我们此刻的 dp_{\ i} ，在下一次（第 i-1 次）转移后就将成为 dp_{\ (i+1)-1} ，所以应向后推一位，从原来的 (1,1) 位置后推到 (2,1) 位置。

这一过程在做其他矩乘题里必然也经常用到，对于第 i(i\neq 1) 行，我们在 (i,i-1) 位置设为 1 ，其余位置设为 0 。

这样可以做到原来在 (1,1) 的第 dp_{\ i} 位在转移后移至 (1,2) 。

对于后面几位亦如此。

最终成品转移矩阵如下（中间省略了一部分数值）：

\begin{bmatrix}1&1&\cdots&0&0\\1&0&\cdots&0&0\\0&1&\cdots&0&0\\\vdots&\vdots&\ddots&\vdots&\vdots\\0&0&\cdots&1&0\end{bmatrix}

所以 AC 此题，流程如下：

  1. 预处理 dp_{\ 100} ，填入原始矩阵。

  2. 初始化转移矩阵。

  3. 矩阵快速幂。

  4. 输出最终答案矩阵的 (1,1) 。

以下是代码～

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9 + 7;
int LEN, PR, NF;
map<int, int> m1, m2;
int N;
int dp[107];

/*矩阵组件*/
struct matrix
{
    int num[107][107];
    matrix operator*(const matrix a) const
    {
        matrix c;
        memset(c.num, 0, sizeof(c.num));
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                for (int k = 1; k <= N; k++)
                {
                    c.num[i][j] = (c.num[i][j] + (num[i][k] * a.num[k][j]) % MOD) % MOD;
                }
            }
        }
        return c;
    }
} ORZ, RBQ;//ORZ----原始矩阵 RBQ----转移矩阵

/*快速幂组件*/
matrix quick_pow(matrix a, int p)
{
    if (p == 1)
    {
        return a;
    }
    matrix tmp = quick_pow(a, p / 2);
    if (p % 2 == 0)
    {
        return tmp * tmp;
    }
    else
    {
        return tmp * tmp * a;
    }
}

signed main()
{
    memset(ORZ.num, 0, sizeof(ORZ.num));
    memset(RBQ.num, 0, sizeof(RBQ.num));
    cin >> LEN;
    cin >> PR;
    for (int i = 1; i <= PR; i++)
    {
        int num;
        cin >> num;
        m1[num] = 1;
    }
    cin >> NF;
    for (int i = 1; i <= NF; i++)
    {
        int num;
        cin >> num;
        if (m1[num])
        {
            m2[num] = 1;//指这个块长两人是否都公认
        }
    }

    /*初始化转移矩阵*/
    for (int i = 1; i <= 100; i++)
    {
        if (m2[i] == 1)
        {
            RBQ.num[1][i] = 1;
            N = i;
        }
    }
    for (int i = 1; i < N; i++)
    {
        RBQ.num[i + 1][i] = 1;
    }

    /*预处理dp[100]*/
    dp[0] = 1;
    for (int i = 1; i < N; i++)
    {
        for (int j = 1; j <= i; j++)
        {
            if (m2[j] == 1)
            {
                dp[i] = (dp[i] + dp[i - j]) % MOD;
            }
        }
        ORZ.num[N - i][1] = dp[i];
    }

    ORZ.num[N][1] = 1;
    matrix ans = quick_pow(RBQ, LEN - N + 1) * ORZ;
    cout << ans.num[1][1];
}