题意
一堆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)代表总数量,那么我们可以把这些矩形分为两类:
- 头部为不可切矩形的一端
- 头部为完美矩形的一端
其实也就是有没有小砖。
然后,我们可以往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
再丢到运算里面,这个不能忘记了。