Tiles 题解

思路

设当前一行有 $w$ 块瓷砖，到达各块瓷砖的方案数为 $f_0,f_1,\ldots,f_{w-1}$。

当下一行增加一块瓷砖时，杨辉三角关系给出新状态 $g_j=f_{j-1}+f_j$，越界项视为零；当下一行减少一块瓷砖时，$g_j=f_j+f_{j+1}$。小规模可以完全按照这个关系逐行模拟。

考虑一次完整的“增加 $a$ 行、减少 $b$ 行”。若组前位置为 $k$，组后位置为 $j$，在中间最宽处枚举位置 $x$，路径数为

$$\sum_x {a\choose x-k}{b\choose x-j}.$$

把第二个组合数的下标取补集并使用范德蒙德卷积，可得

$$\sum_x {a\choose x-k}{b\choose x-j}={a+b\choose b+j-k}.$$

因此一组变化后的动态规划为

$$f'_j=\sum_k f_k {a+b\choose b+j-k}.$$

由于 $\lvert a_i-b_i\rvert\le5$，处理完前 $i$ 组后的行宽至多为 $1+5i$。第二子任务可以对 $j,k$ 二重枚举，直接计算上式。

满分算法把上式视为卷积。旧行宽为 $w$，新行宽为 $w'$，定义

$$h_{d+w-1}={a+b\choose b+d},\qquad 1-w\le d<w'.$$

则普通卷积 $f*h$ 的第 $j+w-1$ 项恰好等于 $f'_j$。模数 $998244353$ 支持 NTT，每组做一次卷积即可。

做法

读入全部 $a_i,b_i$，预处理阶乘与逆阶乘直到 $\max(a_i+b_i)$，从而在 $O(1)$ 时间求组合数。

初始状态只有一项 $f_0=1$。依次处理每一组：根据当前宽度和 $a_i-b_i$ 算出新宽度，构造所需范围内的组合数核 $h$，进行 NTT 卷积，并截取下标从 $w-1$ 开始的连续 $w'$ 项作为新状态。全部处理后将最后状态的所有项求和。

独立满分复核程序使用另一套位逆序和蝶形实现；中档复核程序直接做二重循环；小档复核程序逐行模拟杨辉转移。

复杂度

设道路最大行宽为 $W$，总行数变化量为 $R=\sum_i(a_i+b_i)$。逐行模拟的时间复杂度为 $O(RW)$，空间复杂度为 $O(W)$。

直接组转移的时间复杂度为 $O(nW^2)$，在 $W=O(n)$ 下可写为 $O(n^3)$；空间复杂度为 $O(W+\max(a_i+b_i))$。

NTT 算法的时间复杂度为 $O(nW\log W+\max(a_i+b_i))=O(n^2\log n+\max(a_i+b_i))$，空间复杂度为 $O(W+\max(a_i+b_i))$。