题解：CF2048G Kevin and Matrices

· · 题解

*2800。

最小值小于等于最大值不咋好做，考虑用总方案数减不合法的方案数。不合法就是每行最大值都 >RHS。设 g_i 表示钦定 i 行最大值 \le RHS 的方案数量。答案就是 v^{nm}-\sum_{i=0}^n (-1)^i g_i。

设 f_{i,j} 表示 RHS=j 且钦定了 i 行的最大值 \le j 的方案数量，有 g_j=\sum_{i=0}^n f_{i,j}(-1)^i。

考虑 f_{i,j} 怎么算。枚举有 k 列最小值取到 j，剩下的列最小值要求 <j。钦定的行和选的 k 个列的交点只能填 j，k 列剩下的 k(n-i) 个位置可以填任意 \ge j 的数，未选的 m-k 列每一列方案数都是 j^i v^{n-i}-(v-j+1)^{n-i}，含义是所有钦定的行之外的 n-i 个数任意，钦定的行 \le j，如果所有钦定的行都是 j 则要求剩下 n-k 行至少有一行 <j。可以得到（最后一行是二项式定理）：

\begin{aligned} f_{i,j} &= \binom{n}{i}\sum_{k=1}^m \binom{m}{k}(v-j+1)^{k(n-i)}(j^i v^{n-i}-(v-j+1)^{n-i})^{m-k} \\ &= \binom{n}{i}\left [\sum_{k=0}^m \binom{m}{k}(v-j+1)^{k(n-i)}(j^i v^{n-i}-(v-j+1)^{n-i})^{m-k}\right]-(j^i v^{n-i}-(v-j+1)^{n-i})^m \\ &= \binom{n}{i}\left [j^{im}v^{(n-i)m}-(j^i v^{n-i}-(v-j+1)^{n-i})^m \right] \end{aligned}

这个式子在 i=0 会有问题，可以单独给 i=0 写一个式子，不过注意到 g_0=v^{nm}，答案其实就是 \sum_{i=1}^n(-1)^{i+1}g_i，这样就避免了这个问题。