题意
一堆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再丢到运算里面，这个不能忘记了。