「EGOI2022」Lego Wall / 乐高墙
首先我们可以想到一个 dp 的思路，就是设 \(f[i][j]\) 表示 第 \(i\) 列中有 \(j\) 个 \(2\times1\times1\) 的积木块的前半个。转移是 \(f[i][j]=\sum_{k=1}^{h-j}f[i][k]\times\binom{h-k}{j}\)。但是这个 dp 时间复杂度是 \(O(wh^2)\)。
我们可以思考另一个思路。我们发现，如果不考虑连通的问题，那么方案就是斐波那契数列的 \(h\) 次方，即 \(fib[w]^h\)。那么我可以对第一个断开的位置容斥，设 \(g[i]\) 表示长为 \(i\) 的积木块的方案数，转移是 \(g[i]=fib[i]^h-\sum_{j=1}^{i-1} fib[j]\times g[i-j]\)。时间复杂度是 \(O(w^2)\)。
这两个做法都不能通过这题，但我们可以考虑将这两种做法拼在一块，如果 \(w\le h^2\)，那么就跑第一种做法，否则就跑第二种做法。