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\) 的方案数。
发现后面一坨可以二项式定理：
\[\sum_{j=1}^{n}\binom{n}{j}f(i)^jg(i+1)^{n-j}=(f(i)+g(i+1))^n-g(i+1)^n
\]
然后就可以求啦，时间复杂度 \(\mathcal{O}(n+m\log n)\)。