首先看到这题首先可以想到应该和奇偶性相关……
然后就没有一点思路了，遂看题解
首先，可以观察到结果和实际的高度无关，之和高度的奇偶性有关。
这个很好理解，因为我们可以用操作\(2\)使得在同奇偶性的数域内变化。
因此我们只考虑操作\(1\)
这里要知道一个结论：如果\(a_{i,j}\)为奇数的个数\(cnto\)或\(a_{i,j}\)为偶数的个数\(cnte\)中有一个是偶数，则一定有解；否则一定无解。
证明的话我们可以直到如果对个数为偶数的那些数进行操作\(1\)，则必然可以把他们都变成奇偶性相同的数，因此我们就可以直接进行操作\(2\)了
因此我们分情况讨论：
- 若\(nm\)为奇数，则显然无论怎么选，\(a_{i,j}\)中为奇数的或偶数的个数都一定有一个是偶数，因此答案就是
直接跑一个快速幂即可
- 若\(nm\)为偶数，则我们要保证\(a_{i,j}\)中为奇数的个数和偶数的个数都为偶数才行，因此我们可以得到一个比较暴力的计算方法：
其中\(O,E\)分别表示\([L,R]\)中为奇数和偶数的数的个数
我们发现这个式子和什么很像？二项式定理！
\[\begin{align} (O+E)^{nm} &= \sum_{i=0}^{nm}{ \binom{nm}{i}O^{i}E^{nm-i} } \\ &= \sum_{i=0}^{\frac{nm}{2}}{ \binom{nm}{2i}O^{2i}E^{nm-2i} } + \sum_{i=1}^{\frac{nm}{2}}{ \binom{nm}{2i-1}O^{2i-1}E^{nm-2i+1} } \end{align} \]但其中奇数的部分我们是不想被算的，我们要怎么去除呢？
还是二项式定理！
\[\begin{align} (O-E)^{nm} &= \sum_{i=0}^{nm}{ (-1)^{i}\binom{nm}{i}O^{i}E^{nm-i} } \\ &= \sum_{i=0}^{\frac{nm}{2}}{ \binom{nm}{2i}O^{2i}E^{nm-2i} } - \sum_{i=1}^{\frac{nm}{2}}{ \binom{nm}{2i-1}O^{2i-1}E^{nm-2i+1} } \end{align} \]因此我们发现有：
\[\sum_{i=0}^{\frac{nm}{2}}{ \binom{nm}{2i}O^{2i}E^{nm-2i} } = \frac{(O+E)^{nm} + (O-E)^{nm}}{2} \]最终复杂度\(O(\log{nm})\)
\(p.s.\)这题有一个细节：当你WA on #57时，要知道快速幂里用欧拉定理时特判\(a=0\)的情况，如下数据：
998244352 2 1 998244353
其中\(a^b = 0^{998244352 \times 2} \neq 0^0\)，因此应该返回\(0\)
标签：CF1332E,frac,nm,sum,Same,Height,偶数,binom,2i From： https://www.cnblogs.com/fox-konata/p/17700580.html