题目分析

我们需要计算用 $1 \times 1$ 和 $2 \times 1$ 两种积木搭建 $w \times h$ 墙的方案数，要求：

1. 无空洞（完全覆盖）
2. 连通（所有积木通过上下堆叠关系连通）

算法思路

核心观察

• 每列的高度分布形成某种序列
• 连通性要求限制了高度变化的模式
• 问题转化为带约束的序列计数

两种解法

代码根据数据规模采用两种不同方法：

方法1：$n \leq 5000$ 时的动态规划

w[0] = w[1] = 1;
for (int i = 2; i <= n; i++)
    w[i] = (w[i - 1] + w[i - 2]) % mod;  // Fibonacci序列
for (int i = 1; i <= n; i++)
    w[i] = ksm(w[i], m);  // w[i]^m

dp[0] = mod - 1;
for (int i = 1; i <= n; i++)
    for (int j = 0; j < i; j++)
        dp[i] = (dp[i] + 1ll * dp[j] * (mod - w[i - j])) % mod;

思路：

• w[i]：宽度为 $i$ 的单列铺砖方案数的 $m$ 次方
• dp[i]：宽度为 $i$ 的合法墙方案数
• 使用容斥原理排除不连通的情况

方法2：$n > 5000$ 时的组合数学

for (int i = 0; i <= m; i++)
    f[i] = C[m][i];  // 初始二项式系数

for (int i = 1; i < n; i++) {
    for (int j = 0; j <= m; j++) g[j] = 0;
    for (int j = 1; j <= m; j++)
        if (f[j]) {
            for (int k = 0; k <= m - j; k++)
                g[k] = (g[k] + 1ll * f[j] * C[m - j][k]) % mod;
        }
    for (int j = 0; j <= m; j++)
        f[j] = g[j];
}

思路：

• 利用高度 $m$ 相对较小的特点
• 通过组合数递推计算方案数
• $f[j]$ 表示某种高度分布的方案数

代码详解

快速幂

int ksm(int x, ll y) {
    int ret = 1;
    while (y > 0) {
        if (y & 1) ret = (1ll * ret * x) % mod;
        x = (1ll * x * x) % mod;
        y >>= 1;
    }
    return ret;
}

组合数预处理

for (int i = 0; i < M; i++) {
    C[i][0] = 1;
    for (int j = 1; j <= i; j++)
        C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod;
}

主逻辑分支

根据 $n$ 的大小选择不同算法，充分利用题目约束 $w \times h \leq 500000$。

算法正确性

方法1的正确性

• 单列方案数确实是 Fibonacci 数列：$f(i) = f(i-1) + f(i-2)$
• 容斥原理确保只计算连通方案
• 时间复杂度：$O(n^2)$，适合 $n \leq 5000$

方法2的正确性

• 利用 $m$ 较小的特点进行组合计数
• 通过二项式系数递推计算
• 时间复杂度：$O(n \times m^2)$，当 $m$ 较小时高效

复杂度分析

• 方法1：$O(n^2 + n \log m)$
• 方法2：$O(n \times m^2)$
• 在约束 $w \times h \leq 500000$ 下均可行

总结

这道题的解法体现了根据数据范围选择算法的思想：

• 小宽度：使用动态规划+容斥
• 小高度：使用组合数学递推

两种方法都巧妙地利用了问题的特殊结构，避免了直接处理复杂的连通性约束。