E. Height All the Same——Codeforces Round #630 (Div. 2)

E. Height All the Same

給出\(n * m\)的方格，每個方格上面可以放置立方體，初始時坐标為\((i,j)\)的方格上有\(a_{i,j}\)個立方體，現在有兩個操作:

選擇相鄰的兩個方格并在每個方格上面放置一個立方體

選擇一個人方格并在這個方格上放置兩個立方體

要求在有限次操作内使得每個方格上的立方體數量相等。

現在給出\(a_{i,j}\)的取值\([L,R]\)，問你有多少種初始數量的方案可以滿足上述要求。

因為操作可以任意次，是以不需要考慮具體操作次數，并且可以發現我們可以通過操作\(1\)做到選擇任意兩個方格進行加\(1\)的操作。

然後就是想到因為最後數量需要一樣，每次都是加\(1\)或者加\(2\)，是以考慮初始狀态的奇偶性。假設全是奇數或者全是偶數，則可以通過操作\(2\)完成目标。

假設初始時有\(x\)個奇數，\(y\)個偶數。

因為操作\(2\)不會改變整體方格上立方體數量的奇偶性，隻有在奇偶性相同的方格上進行操作\(1\)，才會改變整體的奇偶性，如：選擇兩個奇數數量的方格進行操作1，則整體奇數數量會減\(2\)，偶數數量會加\(2\)，而選擇奇偶性不同的方格操作相當于沒變（奇偶性不發生該改變）。

并且每次更改都是\(2\)，是以初始奇數的數量或者偶數的數量一定要有一個是偶數，這樣才可以滿足要求。

如果\(n * m\)是奇數，那麼奇數和偶數中一定有一個的數量是偶數，答案直接就是 \((R - L + 1)^{n * m}\)

如果是偶數，則需要計算，利用組合數學得出\(\sum_{i = 0}^{n * m} C_{n * m}^i * x^i * y^{(n * m - i)} * [i \% 2 = 0]\)

對于第二種情況，

根據二項式定理可得：\((x - y) ^{(n * m)} = \sum_{i = 0}^{n * m} C_{n * m}^{i} x^i * y^{(n *m - i)} * (-1)^{n * m - i} = \sum_{i = 0}^{n * m} C_{n * m}^{i} x^i * y^{(n *m - i)} * (-1)^{i}\)

是以奇數項是\(-1\)，偶數項是\(1\)，我們隻要求出偶數項的值即可。

\((x + y)^{n*m} = \sum_{i = 0}^{n * m} C_{n * m}^{i} x^i * y^{(n *m - i)}\)

是以\(ans = \cfrac{(x-y)^{n * m} + (x + y^{n * m})}{2}\)

故：

當\(n *m\)是奇數時，\(ans = (R - L + 1)^{n * m}\)

否則\(ans = \cfrac{(x-y)^{n * m} + (x + y^{n * m})}{2}\ \ (x為奇數出現的數量，y為偶數出現的數量)\)

Code will change the world !