E - Max Matrix 2
一道很具有 ACM 风格的贪心构造。
不难想到倒序放值，假设当前放的值是 \(v\)，放入时需要考虑 \(3\) 种情况：
- \(v\) 在 \(X,Y\) 中均出现：放置位置是唯一的，直接放就行。
- \(v\) 只在 \(X,Y\) 中的某一个出现（这里假设只出现在 \(X\) 中）: 可以将 \(v\) 放在其所在行中的任意一个已经存在最大值的列且空闲的位置。
- \(v\) 均未在 \(X,Y\) 中出现：可以将 \(v\) 放在任意一个已经存在最大值的行与已经存在最大值的列且空闲的位置。
实现细节和复杂度优化见代码。
code
F - 1122 Subsequence 2
很简单的子序列计数，计数思路不难，难点在于最终得到的组合数式子的计算：
\[\sum_{i=1}^{min(p,q)}C_{p-1}^{i-1}*C_{q}^{i}
\]
查了资料发现，这个东西就是范德蒙德卷积板子题。
范德蒙德卷积：
\[\sum_{i=0}^{min(a,k)}C_{a}^{i}*C_{b}^{k-i}=C_{a+b}^{k}
\]
证明可以利用组合意义来证：考虑一个大小为 \(n+m\) 的集合，选出 \(k\) 个数，方案数 等价于 将集合划分成两个大小分别为 \(n\) 与 \(m\) 的集合，从前者取出 \(i\) 个数，后者取出 \(k-i\) 个数，所有可能且合法的 \(i\) 的方案数之和。
将推导出的组合数式子用范德蒙德卷积化简：
\[\sum_{i=1}^{min(p,q)}C_{p-1}^{i-1}*C_{q}^{i} =
\sum_{i=1}^{min(p,q)}C_{p-1}^{i-1}*C_{q}^{q-i} =
C_{p+q-1}^{q-1}
\]
这样，枚举每个断点时，就可以 \(O(1)\) 计算贡献，总复杂度 \(O(n)\)。
code
oi-wiki 范德蒙德卷积
G - Substring Game
SAM，等学完板子后再补~
code