Link:
http://www.codeforces.com/contest/204/problem/D
今天終於完成了一道卡了很久的題，一條關於DP和少量combinatorics的題。這一題其實有一點像那時候
Lucky Pair的概念。
說說題解吧，雖然主要是根據tutorial入面的做法，但細節上很多要處理。
大體想法是不想重覆計算黑白字串的數目，所以黑和白分別用state來表示，fb(pos)代表在pos的時候，包括pos在內的左邊都不含連續k個黑 [反之便是，fw(pos)代表右邊不含連續k個白]，這是Step 1。
之後便可以利Step 1的結果，知道gb(pos)︰包括pos在內，往左數k個字符都是黑，且左邊不可以有任何連續k個黑的字串 (i.e.不可能連續k+1個黑)；白色照樣以gw(pos)表示，同樣左右換轉。這是Step 2。
有了Step 2的結果，便可以滾動的形式，計算最終答案。這是Step 3。
下面是每一個Step的細節。
Step 1:
很明顯，當字串是1-based，fb(0) = 1 (一個空字串不可能有連續k個黑)。假設fb(pos-1)是對的，接著看fb(pos)。如s[pos]是X，fb(pos) = fb(pos-1)*2，否則fb(pos) = fb(pos-1)，這一部份易懂。
(1) 如果在最後k個字符包含一個必為白的字符，那就不用做任何減法，任何選法都不可能造成連續k個黑。
(2) 如果pos-k個字符是黑，這也不用減法，因為當後面全是黑色時，便會有連續k+1個黑，不符fb的原則。
(3) 否則便要把最後k個都是黑的可能性減去，即是fb(pos) -= fb(pos-k-1)。
(4) 一個例外，便是當pos = k時，也要減去1。
細心留意(1)，要precompute多一樣東西，便是sumw(pos)，代表由1到pos之間有多少個白色，這樣才可以在O(1)時間完成。
Step 2:
有了fb和fw，很容易便知道gb(pos)，即最後有k個連續黑，且之前皆沒有其他的連續k個黑。這個數即是fb(pos-k)，而後面只有一種方法令全是黑。
注意數種情況︰
(1) 如當中其中一個必為白，gb(pos) = 0。
(2) 如s[pos-k]為黑，那gb(pos) = 0，原因同Step 1的(2)一樣。
(3) 如s[pos-k]為X，那gb(pos) = fb(pos-k-1)，原因和Step 1的(3)一樣。
Step 3:
由於字串長度可達1000000，所以要快速結合gb和gw的結果。
頹方法是先fix了gb和gw，再把乘積加起來。
for (int i=k; i<n; i++)
for (int j=i+1; j<=n-k; j++)
ret += gb[i]*gw[j]*num_of_X_between(i,j);
但這是O(N^2)，所以我們可以倒轉來做。Fix了一個gb(pos)，再以total儲存後面所有valid的gw的可能性，以滾動方式乘以gb(pos)，達致O(N)。
注意，當total遇到X時，全部乘以2，再加上gw(pos)。寫出來大約是︰
for (int i=n-k-1; i>=k; i--) {
if (s[i] == 'X') total *= 2;
total += gw[i+1];
ret += total * gb[i];
}
這樣就完成了！
.jpg)
.jpg)
