考虑如何计算操作后的奇数个数。
假设在行操作了\(i\)，列操作\(j\)次。
由补集转化，操作后奇数个数\(=im+jn-ij\)
令\(f_i\)表示为行操作\(i\)次的答案，\(g_i\)表示列操作\(i\)次的答案，则答案就是符合要求的所有\(f_i*g_j\)。
列出答案的EGF。
由于每行是相同的，强制让选择的\(i\)行在网格的前\(i\)行
\(f_i=({e^x-e^{-x}\over 2})^i*({e^x+e^{-x}\over 2})^{n-i}[x^q]*q!*C_n^i\)。
后面的\(C_n^i\)表示选择的方案数。
\(f_i=2^n(e^x-e^{-x})^i*(e^x+e^{-x})^{n-i}[x^q]*q!*C_n^i\)
如果使用二项式定理展开\((e^x-e^{-x})\)和\((e^x+e^{-x})\)，再暴力进行多项式乘法，则生成一个\(2n\)次关于\(e^x\)的多项式（指数可能是负的），时间复杂度\(O(n^3)\)
但是注意到\(f_{i+1}\)的后面的项等于\(f_i\)的多项式乘以\((e^x-e^{-x})\)再除以\((e^x+e^{-x})\)，所以可以在\(O(n)\)的时间内得到下面的多项式，时间复杂度\(O(n^2)\)。
\(g\)可以同理计算。
考虑容斥。（CTS2019 珍珠）
令\(h_i\)表示钦定至少\(i\)行为为奇数，其它任意。
列出答案的EGF。
则\(h_i=\sum C_i^j*g_j\)。
\(h_i=({e^x-e^{-x}\over 2})^i*e^{x(n-i)}[x^q]*q!*C_n^i\)
\(h_i=2^i({e^x-e^{-x}})^i*e^{x(n-i)}[x^q]*q!*C_n^i\)
\(h_i=2^i\frac{1}{e^{xi}}({e^{2x}-1})^i*e^{x(n-i)}[x^q]*q!*C_n^i\)
\(h_i=2^i({e^{2x}-1})^i*e^{x(n-2i)}[x^q]*q!*C_n^i\)
\(h_i=C_n^i2^i\sum_{j=0}^{i}e^{2j}(-1)^{i-j}e^{x(n-2i)}[x^q]*q!C_{i}^j\)
\(h_i=C_n^i2^i\sum_{j=0}^{i}(-1)^{i-j}e^{x(n-2i+2j)}[x^q]*q!C_{i}^j\)
\(h_i=C_n^i2^i\sum_{j=0}^{i}(-1)^{i-j}e^{x(n-2(i-j))}[x^q]*q!C_{i}^j\)
\(h_i=C_n^i2^ii!\sum_{j=0}^{i}(-1)^{i-j}((n-2(i-j))^q\frac{1}{(i-j)!j!}\)
令\(a_i=(-1)^i((n-2(i-j))^q\frac{1}{i!},b_i=\frac{1}{i!}\)
则\(a*b=h\)
考虑二项式反演，\(g_i=\sum_{j\geq i}C_{j}^i(-1)^{j-i}h_j=\frac{1}{i}\sum_{j\geq i}\frac{j!}{(j-i)!}(-1)^{j-i}h_j\)
令\(a_i=(-1)^i\frac{1}{i},b_i=i!h_i\)
则\(a,b\)的减法卷积就是\(h\)。
计算答案考虑\(im+jn-ij\leq k\)
则\(j(n-2i)\leq k-im\)
根据\((n-2i)\)的正负性分类讨论，使用前缀和计算。
时间复杂度\(O(n\log_2n)\)
原文：https://www.cnblogs.com/ctmlpfs/p/14141967.html