Hitachi2020 E
看到 \(\oplus\) 操作和\(2^n-1\)时猜结论 \(ans_{i,j}=\operatorname{popcount}(i\& j)\bmod 2\)，过不去，然后就不会了。
然而令答案的二维前缀和为 \(\operatorname{popcount}(i\& j)\bmod 2\)是合法的，二维差分就行了。证明如下。
不妨设 \(n\ge m\)，\(x=2^n,y=2^m\) 则有 答案上界为 \(\frac{x^2y(y-1)}{8}\)。原因：矩阵第二维端点共有 \(\frac{y(y-1)}2\) 种取值，对每种取值分开考虑，设为\((j_1,j_2)\)，则当且仅当 \(S(1,i_1-1,j_1,j_2)\oplus S(1,i_2,j_1,j_2)=1\) 时合法，即方案数为\(S(1,x,j_1,j_2)=0\) 的个数乘 \(S(1,x,j_1,j_2)=1\) 的个数，后者最多为 \((\frac{x}2)^2\)，相乘即得答案。
考虑 \(n=m\) 的情况，答案为\(\frac{8^n(2^n-1)}8\)。
设二维前缀和为 \(s_{i,j}\)，为简化式子记 \(|x|=\operatorname{popcount}(x)\bmod 2\)，则\((i,j,k,l)\)合法当且仅当\((i+1,j+1,k,l)\)构成合法矩阵，即 \(|s_{i,j}\oplus s_{i,l} \oplus s_{k,j} \oplus s_{k,l}|=1\)。\(\oplus\) 操作可以放进 \(|x|\) 操作里，因此原式等价与 \(|(i\&j)\oplus (i\&l)\oplus (k\&j)\oplus (k\&l)|=1\)。先无视 \(i<k,j<l\) 的限制，最后答案除以 \(4\)（矩阵合法时\(i\neq k\land j\neq l\)，因此可以忽略等于的情况）。
对每一位分开考虑，当且仅当 \(i,k\) 中恰有一个该位为 \(1\)，\(j,l\) 中恰有一个该位为 \(1\) 时该位 \(\oplus\) 值为 \(1\)，共 \(4\) 种方案。
因此答案为（枚举 \(1\) 的个数）
\[\sum_{i=0}^n[2\nmid i]\binom n i 4^i12^{n-i}\\ =\sum_{i=0}^n\frac{1+(-1)^i}{2}\binom n i 4^i12^{n-i}\\ =\frac{1}{2}(\sum_{i=0}^n\binom n i 4^i12^{n-i}-\sum_{i=0}^n\binom n i(-4)^i12^{n-i})\\ =\frac{16^n-8^n}{2}=\frac{8^n(2^n-1)}{2} \]上文提到要除以 \(4\) ，因此结果为 \(\frac{8^n(2^n-1)}{8}\)，得证。
\(n>m\) 时 \(i,k\) 还有额外的 \(n-m\) 位填，由于 \(j,l\) 该位为 \(0\)，因此这些位不会影响奇偶性，答案为\(\frac{8^m(2^m-1)4^{n-m}}{2}=\frac{4^n2^m(2^m-1)}{8}\)，符合上界。
标签：frac,Sum,binom,i12,答案,oplus,Hitachi2020E,Rectangles,sum From： https://www.cnblogs.com/Nikrot/p/16908320.html