Descirption

Solution

若定义 \(f(k)\) 为一行有 \(k\) 个 \(1\) 的方案数，则 \(\displaystyle f(k)=\binom{m}{k}x^ky^{m-k}\)。

则 \(\displaystyle E=\sum_{i=0}^{m}i\sum_{j=1}^{n}\binom{n}{j}f(i)^j\left(\sum_{k=i+1}^{m}f(k)\right)^{n-j}\)。

不妨设 \(\displaystyle g(k)=\sum_{k=i+1}^{m}f(k)\)，\(g(k)\) 的意义就是一行至少有 \(k\) 个 \(1\) 的方案数。

发现后面一坨可以二项式定理：

然后就可以求啦，时间复杂度 \(\mathcal{O}(n+m\log n)\)。