#41 P14461
首先，我们注意到原 \(F,G\) 的转移是相对独立的，于是我们分开讨论。我们先手玩一下，看随着变换过程，\(f_i\) 怎么变。
然后发现第 \(k\) 项都形如 \(\prod \limits_{j=1}^k(i+j)\times f_{i+k}\)。
然后，我们观察系数，发现在 \(2j\) 次时，系数都形如 \(\binom{i}{j}\) 和 \((-1)^i\) 的乘积。
然后就直接算就完了。
#42 ARC118E
题目传送门
首先，这类题目有一个很明显的特征：如果确定状态求答案简单，但是时间复杂度不支持枚举。
那么这时候就需要考虑边转移边维护容斥系数。
我们记 \(f_{x,y,k,a,b}\) 表示已经到 \((x,y)\) 且已经经过了 \(k\) 钦定的障碍点，且当前行有（没有）确定的障碍点，当前列有（没有）确定的障碍点。
那么我们考虑转移：
-
若 \((x,y)\) 是一个确定的障碍点：那么不转移；
-
如果不是：
-
若 \(x \le n\) ：
- 不钦定 \((x,y)\) 为障碍点：\(f_{x+1,y,k,a_{x+1},b} \leftarrow f_{x,y,k,a,b}\)
- 钦定 \((x,y)\) 为障碍点：\(f_{x+1,y,k+1,a_{x+1},1} \leftarrow f_{x,y,k,a,b}\)。
-
若 \(y \le n\)：类似，不赘述。
-
最后我们假设 \(m\) 为初始时 \(-1\) 的数量，那么答案为：
\[\sum_{i=0}^m(-1)^if_{n+1,n+1,i,0,0}\times (m-i)!
\]
最后一项是因为没有钦定的位置可以任选。