🐎 | CF2048G
Pawbert
·
·
题解
容易发现 LHS 必定 \ge RHS，因为对于任意第 i 行和第 j 列，一定有第 i 行的 \max \ge a_{i,j}\ge 第 j 列的 \min。于是我们只要算出相等的方案数就好了，这个非常傻逼，直接容斥，每次钦定 i 行 j 列，枚举这个相等的值 x，答案就是：
\sum\limits_{x=1}^V\sum\limits_{i=1}^n\sum\limits_{j=1}^m(-1)^{i+j}\dbinom{n}{i}\dbinom{m}{j}x^{i(m-j)}(V-x+1)^{j(n-i)}V^{(n-i)(m-j)}
已经可以 \mathcal O(n^2V) 计算了，把 i 的系数提出来：
\sum\limits_{x=1}^V\sum\limits_{i=1}^n(-1)^i\dbinom{n}{i}\sum\limits_{j=1}^m\dbinom{m}{j}(-1)^jx^{i(m-j)}(V-x+1)^{j(n-i)}V^{(n-i)(m-j)}
后面那坨很像二项式定理，合并一下：
\sum\limits_{x=1}^V\sum\limits_{i=1}^n(-1)^i\dbinom{n}{i}\sum\limits_{j=1}^m\dbinom{m}{j}[-(V-x+1)^{(n-i)}]^j[x^iV^{(n-i)}]^{m-j}
\sum\limits_{x=1}^V\sum\limits_{i=1}^n(-1)^i\dbinom{n}{i}[x^iV^{(n-i)}-(V-x+1)^{(n-i)}]^m-\Delta
后面那个 \Delta 就是为了凑二项式定理要把 j=0 的算进去，然后最后减掉的东西，时间复杂度 \mathcal O(nV\log V)。