Week 4
Tuesday（1.20）
P3092 [USACO13NOV] No Change G
水题（但我为什么数组开小了呢）
不难发现，\(k\) 的值很小，我们可以考虑状态压缩。
令 \(f_i\) 表示我状态为\(i\) 时我能走到的最大距离，最后用二分和前缀和优化即可。
Wednesday（1.21）
P5664 [CSP-S 2019] Emiya 家今天的饭
很好的题，我们可以考虑正难则反，发现如果没有第二个约束条件，那么答案就是 \(\prod _{i=1} ^{n} (num_i+1)-1\)，其中 \(num_i\) 就是第 \(i\) 排的和。
我们来考虑什么时候不合法。
不难发现，如果一个方案不合法只会有一个主要食材的数量越界了，不需要考虑其他的容斥。
由此，我们可以枚举越界的数 \(col\) 并设计出状态：\(f_{i,j}\) 表示对于前 \(i\) 行，\(col\) 中选的数量比其他数多 \(j\) 的方案数。
转移也很好想：
\[f_{i,j}=f_{i-1,j}+f_{i-1,j-1}*a_{i,col}+f_{i-1,j+1}*(num_i-a_{i,col})
\]
最后用方案数减去每一次枚举的 \(col\) 所对应的 \(\sum _{i=n+1} ^{2 \times n} f_{n,i}\) 即可。
注：这里是 \(n+1\) 到 \(2 \times n\) 的原因是在转移中有可能出现 \(j\) 为负数的情况，需要加个偏移量。