<题解>[GXOI/GZOI2019]逼死强迫症

洛谷题面

题意

一堆2×1的砖和两块1×1的砖,两块小砖不能放一起,问拼成2×n的方案数量。

多组数据,T\le 500, N \le 2\times 10^9

分析

分析1

第一反应想到DP

冷静分析一波,包含两块小砖的矩形肯定是酱紫的:

--- --- ---
* --- --- *

--- --- *
* --- ---

上下翻转也可。
反正肯定是连续的(意思是中间不会出现完整的切面),导致长度确定并且要求两端包含小砖的方案数量始终为2,考虑以这个性质做文章。
(下面的文章称这种矩形为不可切矩形

(不包含小矩形的我称为完美矩形

h[0] = 1, h[1] = 1, h[2] = 2, h[3] = 3;
g[3] = 2;
while (T--)
{
    int n = read;
    while (t < n)
    {
        t += 1;
        h[t] = (h[t - 1] + h[t - 2]) % mod;
        g[t] = (g[t - 1] + g[t - 2] + 2) % mod;
    }
    long long ans = 0;
    for (int i = 3; i <= n; ++i)
        ans = (ans + g[i] * h[n - i]) % mod;
    printf("%lld\n", ans);
}

h(i)代表只用完整的砖可以拼出来的2\times i的矩形的方案数量,特别地,为了方便最后面的for,h(0)=1
g(i)代表下端为不可切矩形末端,总矩形为2\times i的总矩形方案数量。

很显然,h(i) = h(i-1) + h(i-2)代表往一个完美矩形一端加一个横杠或者两条竖杠(注意不能往两端加,否则会重复)
然后g(i) = g(i-1) + g(i-2) + 2,代表加1条横杠,加两条竖杠和直接一个长度为i不可切矩形。

最后把完美矩形h插到g后面就是f

为啥想这么复杂?考场上推的时候考虑了太多种方法,都因为重复无法消除影响放弃了,最后只能想到这种肯定没有重复的方法。

分析2

(以下的g(x)为斐波拉契数列,g(0) = g(1) =1, g(2)=2

还是依赖那个分析。

考虑f(i)代表总数量,那么我们可以把这些矩形分为两类:

  1. 头部为不可切矩形的一端
  2. 头部为完美矩形的一端

其实也就是有没有小砖。

然后,我们可以往f(i-1), f(i-2)头部插一块横杠或者两块竖杠,然后接下来考虑头部为不可切矩形的情况。

考虑头部不可切矩形长度从3递减,那么剩余的空间(i-3)留给完美矩形,那么完美矩形个数为\sum\limits_{x=1}^{i-3} g(x) = g(i-1) - 1,每个完美矩形头部可以接2种不可切矩形,总方案数量就是2g(i-1)-2

最后把两部分答案加起来,f(i) = f(i-1) + f(i-2) + 2g(i-1) -2,考虑矩阵快速幂加速,构造5\times 5的转移矩阵,1\times 5的状态矩阵(f(i), f(i-1), g(i), g(i-1), 2)。

\left[\begin{matrix} 1& 1& 0& 0& 0\\ 1& 0& 0& 0& 0\\ 2& 0& 1& 1& 0\\ 0& 0& 1& 0& 0\\ -1&0& 0& 0& 1 \end{matrix}\right]

初始状态矩阵为(i=3)[2\quad 0\quad 3\quad 2\quad -1],然后用这个矩形乘转移矩形的n-3次方,最后的(0,0)就是答案。

代码

#include <cstdio>
#include <cctype>
#include <cstring>
struct Read
{
    //...
} read;

const int N = 10000000, mod = 1000000007;

struct Mat
{
    long long v[5][5];
    Mat() { memset(v, 0, sizeof v); }
    inline Mat operator*(const Mat &b) const
    {
        Mat mt;
        for (int i = 0; i < 5; ++i)
            for (int l = 0; l < 5; ++l)
                for (int j = 0; j < 5; ++j)
                    mt.v[i][l] = ((mt.v[i][l] + v[i][j] * b.v[j][l]) % mod + mod) % mod;
        return mt;
    }
    inline void toBase(void)
    {
        for (int i = 0; i < 5; ++i)
            v[i][i] = 1;
    }
};

const int origin[5][5] = {
    {1, 1, 0, 0, 0},
    {1, 0, 0, 0, 0},
    {2, 0, 1, 1, 0},
    {0, 0, 1, 0, 0},
    {mod - 1, 0, 0, 0, 1}};

inline Mat power(Mat a, int n)
{
    Mat ret; ret.toBase();
    while (n)
    {
        if (n & 1) ret = ret * a;
        a = a * a;
        n >>= 1;
    }
    return ret;
}

int main(void)
{
    int T = read;
    Mat base, st;
    for (int i = 0; i < 5; ++i)
        for (int j = 0; j < 5; ++j)
            base.v[i][j] = origin[i][j];
    st.v[0][0] = 2;
    st.v[0][2] = 3;
    st.v[0][3] = 2;
    st.v[0][4] = 2;
    while (T--)
    {
        int n = read;
        if (n < 3)
        {
            puts("0");
            continue;
        }
        res = st * power(base, n - 3);
        printf("%lld\n", res.v[0][0]);
    }
}

后记

这道题调了一个晚上,最后错误在:1. 矩阵乘法没有交换律; 2. 快速幂if (n & 1)写成了if (n)我在那里想为什么这个矩阵乘法乘出来的东西是一段一段变化的。这篇文章主要是提醒自己。

对了,负数可以先加上一个mod再丢到运算里面,这个不能忘记了。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注