题解：P14367 [JOISC 2018] 帐篷 / Tents

chenzefan · 2026-01-27 20:52:31 · 题解

题目传送门

思路

随机考虑 dp。显然需要 O(HW) 的。

定义 dp_{i,j} 表示 i 行 j 列的方案数。

考虑转移。考虑对于第 i 行而言：

• 不放则删行。方案为 dp_{i-1,j}。
• 放并立即删一行一列。方案为 dp_{i-1,j-1}\times 4j。
• 删两行一列（即之前的 i-1 行每行放一个帐篷）。方案为 dp_{i-2,j-1}\times (i-1)j。
• 放两个帐篷删两列一行。方案为 dp_{i-1,j-2}\times \binom{j}{2}=dp_{i-1,j-2}\times \frac{j(j-1)}{2}。

合并后可知，dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}\times 4j+dp_{i-2,j-1}\times(i-1)j+dp_{i-1,j-2}\times \frac{j(j-1)}{2}。

初始化即 dp_{0,i}=dp_{i,0}=1。

注意开 long long 并取模。