给定一个 \(n\times m\) 的网格图和 \(q\) 个关键点。要求以每个关键点为中心分别放置一个 L 形。要求每个格子至多被覆盖一次。求合法方案数。
L 形：
.@. .@. ... ...
.#@ @#. .#@ @#.
... ... .@. .@.
\[q,n\times m\le10^6
\]
注意到 L 形即为上下恰好选一个，左右恰好选一个。
在关键点上下，左右相邻点之间连边。问题即变为给边定向使得每个点出度至多为 \(1\)。
考虑每一个极大连通子图，若其内有 \(x\) 个顶点，\(y\) 条边：
- \(x<y\)，根据抽屉原理，至少有一条边出度大于 \(1\)，不合法。
- \(x=y\)，对图做拓扑排序，最后必定剩下一个单环，因此恰好有 \(2\) 种方案。
- \(x=y+1\)，此时图是树，以每个点为根都有一种不同的内向定向方案，方案数即为 \(x\)。
- \(x>y+1\)，根据点边容斥这种情况不可能出现。
乘起来就是答案。