3 4 3 2 3 3 3 3 2 3
8 3 HintFor the second example: 0 express face down,1 express face up Initial state 000 The first result:000->111->001->110 The second result:000->111->100->011 The third result:000->111->010->101 So, there are three kinds of results(110,011,101)
這幾天最煩這種，“姿勢對著，就是不過”的題了。。。比賽的時候我想的算法是：“O(NlgN)排序 - O(N)計算答案區間 - O(N)對答案求和”。但是TLE了。。。後來又仔細的想了想，其實根本不需要排序，直接就能O(N)計算答案區間。然後重寫寫了份，糾結了半天的位運算處理奇偶性之後終於過了。
我慢慢一步一步說我的算法是怎麼來的。
這個模型非常的巧妙，因為是卡片的翻轉，那麼每個卡片就有兩種狀態（正面'1'和反面'0'）。
那麼能不能把這個實際例子抽象出來呢？
當然是可以的了！
首先引入符號M(n, k)：表示，n張卡片中，只有k張正面的所有的可能的集合。
其次我引入一種建立在M(n, k)中的元素上的二元運算，翻轉運算，用乘法(*)表示。
為什麼是二元運算呢？我們慢慢地考慮翻轉狀態。“從4張卡片中先翻轉3張。”這句話的意思是不是可以理解成“_M(4, 0) * _M(4, 3)”呢？我用前置的下劃線表示一個這個集合的元素。也就是說，這個表達式就是從沒有正面開始發生狀態轉移，結果我們暫時不考慮，狀態轉移的方法是通過“翻轉3張”這個操作。換句話說，一次乘法運算相當於一種累計翻轉。第一次翻轉的是0張，所以所有的答案是M(4, 0)；第二次翻轉的是3張，所以所有的答案是M(4, 3)。兩次翻轉一累計，就是我們的答案了。
再次強調，一次乘法運算就相當於累計翻轉，當然多次的乘法運算（比如先翻3張，再翻2張，最後再翻3張）也可以看做多次的累計翻轉。即，針對一張特定的卡片，如果它翻轉了偶數次，就相當於沒有翻轉；同樣翻轉了奇數次的就相當於翻轉了一次。
然後這個運算的作用范圍是什麼呢？沒錯，是剛剛定義的符號M(n, k)的所有元素的全體，也就是：G = {x | x ∈ M(n, k), k = 0, 1, 2, 3, ..., n.}。
其次我們接著去關心這個運算的一些性質：（為了方便，以後稱這個運算為乘法）
首先這個運算滿足結合律。即，對任意的G中的元素a, b, c，a * b * c = a * (b * c)。這個不多提，獨立證明。其次這個運算有單位元e = M(n, 0)。即，對任意的G中的元素a， a * e = e * a = a。這個可以簡單地發現。再者這個運算有逆元a-1 = a。即，對任意的G中的元素a， a * a-1 = a-1 * a = e。因為一個翻轉只需再執行一次自己的翻轉就行了。最後這個運算有交換律。即，對任意的G中的元素a, b, c，a * b = b * a。因為翻轉的順序是不定的，可以先翻轉a張，再翻轉b張；也可以先翻轉b張，再翻轉a張。所以，針對G和構建在G上的運算*就是一個阿貝爾群（交換群）。
但是這個代數系統顯然不夠好。我們應當接著去拓展他。
換句話說，剛才，我們僅僅研究兩個元素去做這個運算的性質，現在我們去研究兩個集合，去做這個運算的性質。當然，首先我們從結果入手，嘗試去尋找規律。
比如這次運算：M(n, x1) * M(n, x2)，為了方便分析結果，我們假設x1 >= x2，會產生什麼樣的結果呢？
回歸剛才的定義，M(n, x1)表示有y1 := x1個正面，和y2 := (n - x1)個反面。那麼下一步要對x2個卡片進行翻轉。我們假設，它對i個上一次翻轉過的卡片進行再翻轉，對j個沒有翻轉過的卡片進行翻轉。這樣就有C(y1, i) + C(y2, j)種可能，同時當然還要滿足組合數的公式等等。這裡生成的結果都有什麼呢？假設最後的正面有z個，原本有y1個正面，先減少i個，在增加j個。又因為i + j = x2，x1 >= x2，所以有 x1 - x2 <= z <= min(n, (n - x1) + (n - x2))。而且，如果你是在草稿紙上寫了過程的話，你會發現，本來 z = y1 - i + j = x1 - i + (x2 - i) = x1 + x2 - 2 * i。也就是，z是一個公差為2的等差數列。
為了方便理解，我引入加法符號+，表示集合的並運算。
舉個具體的例子吧：
M(4, 3) * M(4, 2) = M(4, 1) + M(4, 3)
M(8, 5) * M(8, 3) = M(8, 2) + M(8, 4) + M(8, 6) + M(8, 8)
M(8, 4) * M(8, 6) = M(8, 3) + M(8, 5) + M(8, 7)
不知道大家看出一個規律沒有，就是關於結果序列的奇偶性。如果x1與x2同時是偶數，結果是一個奇數的序列；同時為奇數，結果是一個偶數序列；一奇一偶，結果是奇數序列。 還有一個規律，如果有多次的乘法運算，豈不是要對每一個生成的結果進行再一次乘法運算？沒錯的。這裡嚴格意義上，引入加法，就同時引入了分配率的概念，相當於建立了一個環。不過用處不大，只是方便理解而已。回到剛才多次乘法運算的問題，如果每一個都去乘，答案就會很慢很慢，因為這裡相當於進行的是對一個N的數據展開成(N / 2)的一組新數據，會指數爆炸的。但是舉個例子，假設我計算的是這組乘法：
M(8, 4) * M(8, 6) * M(8, 3)
第一次乘法的運行結果時：
M(8, 4) * M(8, 6) = M(8, 3) + M(8, 5) + M(8, 7)
接著去逐項去乘：
M(8, 3) * M(8, 3) = M(8, 0) + M(8, 2) + M(8, 4) + M(8, 6)
M(8, 5) * M(8, 3) = M(8, 2) + M(8, 4) + M(8, 6) + M(8, 8)
M(8, 7) * M(8, 3) = M(8, 4) + M(8, 6)
可以看到，實際上的答案是M(8, 4) * M(8, 6) * M(8, 3) = M(8, 0) + M(8, 2) + M(8, 4) + M(8, 6) + M(8, 8)
換句話說，如果我們記錄上下界，豈不是很方便？這樣就不會一層一層的展開了。
所以問題就被我們抽象成：計算每一層的區間，同時考慮奇偶性。
每一次我都對上一次的答案區間進行更新。其實更准確的說實際上是在檢查是否需要放大區間。特別判斷不在這個區間的x（相當於上文中的M(n, k)中的k）的情況，並且正確的賦值就行，也就是low = 0, high = n。其余的就判斷與當前的區間的邊界的距離，一個取小值，一個取大值。
當然不能忘記處理奇偶性。奇偶性和異或運算很類似，所以我是用異或搞的。
最後因為是一個公差為2的序列，但是我們只記錄了區間和奇偶性。所以應當根據奇偶性去判斷答案。
總體的時間復雜度就是O(N){計算區間} - O(N){計算答案}。
組合數計算公式很簡單。C(n, m) = n! / (m! * (n - m)!)
模運算中，除法a / b，等價於a * b^-1，也就是乘上它的逆。所以我們在預處理時計算出逆元的階乘。
逆元的定義是，滿足a * b % p = 1的b，稱為a的逆元，有時記做b = inv(a)。計算方法很簡單。擴展歐幾裡得還記得不？ax + by = gcd(a, b)。因為相鄰的兩個數必然互素，那麼就可以寫成ax + by = 1。這個不定方程可以和一元線性同余方程互相轉化。所以通過擴展歐幾裡得可以很快的求得逆元。當然也可以直接通過遞推的解法來進行計算。
逆元計算好之後，就是查詢結果了，這個就是注意每次乘法都要取模就好。
