蒟蒻DP太菜了QAQ。
一点体会：DP就是如何通过最少的信息确定最优解。
P5664 [CSP-S2019] Emiya 家今天的饭
思考了一下，发现第3个要求很难直接搞，于是考虑正难则反，用总方案数减去不符合要求的方案数。求总方案数：
\(g_{i,j}\) 表示在前 \(i\) 行中选 \(j\) 个点的方案数，则
\[g_{i,j}=g_{i-1,j}+g_{i-1,j-1}\times s_i \]其中 \(s_i = \sum_{1 \le j \le m} a_{i, j}\) 。最后 \(\sum_{1\le i \le n}g_{n, j}\) 就是总方案数。
求不满足要求的方案数：
枚举超额的列 \(k\) ，\(f_{i, j}\) 表示在前 \(i\) 行且当前列比其余列多 \(j\) 个的方案数，有：
\[f_{i,j} = \begin{cases} f_{i - 1, j} \\ +\\ f_{i - 1,j - 1} \times a_{i,k} \\ +\\ f_{i - 1,j + 1} \times (s_i-a_{i,k}) \end{cases} \]P2167 [SDOI2009] Bill的挑战
首先我们可以发现求出跟其中一个字符串匹配的 \(T\) 的个数，但题目中要求刚好和 \(K\) 串匹配的方案数。之后又可以注意到一个串和 \(A\) 匹配和 \(B\) 不匹配只由 \(A, B\) 中字母位和串的长度决定。考虑状压：
\(f_{i, j}\) 表示 \(T\) 与 \(n\) 个字符串中的 状态 \(j\) 前 \(i\) 位匹配的方案数。我们考虑枚举第 \(i + 1\) 的字符 ch，提前求出 \(g[i][ch]\) 表示n个字符串中第 \(i\) 位为ch的状态，那么有：
\[f_{i+1, j \cap g[i+1][ch]} += f_{i,j} \]另外，我们可以把? 看作一个字符，只不过26种都算而已。