Topcoder SRM 504 DIV 1 Easy + Medium

題目出得不錯，也挺容易，唯獨最後15分鐘伺服器又出問題，不算rating了。Topcoder應該考慮是否調低參賽者的註冊人數，免得同類事故再發生。

Easy: 大意是有一個 $01$ 字串 $S$ 重覆 $K$ 遍，即 $S' = \underbrace{S\cdots S}_{K\text{ times}}$ 。每一回合把 $S'$ 的首個字元拿出來，如果是 $0$ 的話，則把 $S'$ 餘下的元字順序倒換。如果是 $1$ 的話則把 $S'$ 的字元取逆，即 $S'_i := 1 - S'_i$ 。問通過這個過程裡你能抽到多少個 $1$ 的字元。保証 $S'$ 最多帶 $100000$ 個字元。

做法是保留兩個指針兩個變量。指針一指首一指尾，變量決定元素取前或後和數值需否取逆。然後…就是做。或者可以用STL的deque<T>。

Medium：對於一個 $N \times M$ 的 $01$ -板塊，它依如下程序段修改其內容。

For i = 0 to N-2:
    For j = 0 to M-2:
        //Get the current colors of cells (i,j) and (i,j+1)
        A = Grid(i,j) , B = Grid(i,j+1)

        If (A,B) == (0, 0) Then:
             Do nothing.
        EndIf
        If (A,B) == (1, 0) Then: 
             Mark cells (i+1,j) and (i+1,j+1) as 1.
        EndIf
        If (A,B) == (0, 1) Then:
             Mark cells (i+1,j) and (i+1,j+1) as 0.
        EndIf
        if (A,B) == (1, 1) Then:
             Swap the content in cells (i+1,j) and (i+1,j+1).
        EndIf
    EndFor
EndFor

現在有一輸出 $O$ ，問有多少個輸入可以經以上程序段後得出它。答案取模 $1000000007$ 。

留意幾件事即可。

1. 根據程序段，首行是固定的。
2. 第 $1 \le i < N$ 行的結果 $O_i$ 由 $O_{i-1}$ 來決定的，因為本來的輸入已經被程序段毀掉了。
3. 實際是求對於 $0 \le i \le N-2$ 由 $O_i$ 決定 $O_{i+1}$ 的輸入有多少種。
4. 根據程序段，操作是自左向右處理的。只要把 $O_{i+1}$ 自右至左進行逆操作，理應是要求輸入行有哪些字元可以是任意字元。假設該行有 $K$ 個任意字元，那麼結答案則可以再乘上 $2^K$ 。
5. 哪些逆操作可以決定某元素是否任意字元？留意只有 $(0, 1)$ 和 $(1, 0)$ 才會硬把兩個字元改成一種顏色，其逆操作不能判斷原來的字元。 $(1, 1)$ 的逆操作則與本來操作一樣。 $(0, 0)$ 逆操也作就是甚麼都不幹。
6. 甚麼時候是沒有解？就是進行 $(0, 1)$ 和 $(1, 0)$ 的逆操作時對兩個應修改元素的值與進行其操作後不相符。此時大可以回傳0。