那头是头！

· · 题解

1 个月了都没有简单做法，急了。

先考虑怎么求总的方案数。于是先随便设一个 f_{n,m} 为大小为 n\times m 的合法矩阵的方案数。

一个方案合法的条件是对于任意一个 1，它所在的行前缀均为 1 或列前缀均为 1。

所以很自然地枚举当前矩阵最后一行的极长前缀 1 个数，再枚举后面的 1 的位置，合法转移即钦定后面这些 1 的位置对应的列全为 1 的方案数。

可以发现对于一个 n\times m 的矩阵，钦定其中 p 列为 1 的方案与 n\times (m-p) 的矩阵的方案形成双射。

所以直接得到一个 O(nm^3) 的转移。

f_{i,j}=f_{i-1,j}+\sum_{k=0}^{j-1}\sum_{l=0}^{j-k-1}\binom{j-k-1}{l}f_{i-1,j-l}

可以类似转移得到方案的 1 的个数的和。

即

g_{i,j}=g_{i-1,j}+j\times f_{i-1,j}+\sum_{k=0}^{j-1}\sum_{l=0}^{j-k-1}\binom{j-k-1}{l}(f_{i-1,j-l}\times (l\cdot i+k)+g_{i-1,j-l})

交换和式后用上指标求和优化到 O(nm^2)，因为 nm=S\le 2\times 10^5，所以复杂度不超过 O(S\sqrt{S})，可过。

转移是卷积形式还可以优化成 O(nm\log m)，但是不重要了。

感觉至多下位紫，怎么上的铜牌？

我宣布这场 C>A>D。