# 某岛

… : "…アッカリ～ン . .. . " .. .
July 14, 2012

# Codeforces Round #129

### Brief description:

Problem A. Little Elephant and Interval:

Problem B. Little Elephant and Cards:

Problem C. Little Elephant and Furik and Rubik:

Problem D. Little Elephant and Retro Strings:

..

Problem E. Little Elephant and Strings:

### Analysis:

Problem A. Little Elephant and Interval:
..
Problem B. Little Elephant and Cards:
..
Problem C. Little Elephant and Furik and Rubik:
..

Problem D. Little Elephant and Retro Strings:

F1[i]: 恰好以第 i 位结尾，形成长度为 k 的 {BBBBB..} 的数目。
F2[i]: 所有以 i 位结尾，长度 >= k的 {BBBBB..} 串的数目。。
G1[i]: 恰好以第 i 位结尾，形成长度为 k 的 {WWWWW..} 的数目。
G2[i]: 所有以 i 位结尾，长度 >= k的 {WWWWW..} 串的数目。。

Problem E. Little Elephant and Strings:
… ?

```const int N = 1000009;

int F0[N], F1[N], G0[N], G1[N]; char s[N];
int L[N], R[N], n, k, k_, l, r;

int main(){

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif

RD(n, k); RS(s+1); k_ = k + 1;

REP_1(i, n) L[i] = L[i-1] + (s[i]=='X');
DWN_1(i, n, 1) R[i] = R[i+1] + (s[i]=='X');

l = 0, r = 0; REP_1(i, n){
if (s[i] == 'X' || s[i] == 'B') ++r; else l = r = i;
F1[i] = sum(pdt(s[i] == 'X' ? 2 : 1, F1[i-1]), F0[i] = r-l>=k && s[i-k] != 'B' ? dff(pow(2, L[i-k_]), F1[i-k_]) : 0);
}

l = n+1, r = n+1; DWN_1(i, n, 1){
if (s[i] == 'X' || s[i] == 'W') --l; else r = l = i;
G1[i] = sum(pdt(s[i] == 'X' ? 2 : 1, G1[i+1]), G0[i] = r-l>=k && s[i+k] != 'W' ? dff(pow(2, R[i+k_]), G1[i+k_]) : 0);
}

int res = 0; FOR(i, 1, n) INC(res, pdt(F0[i], G1[i+1]));
OT(res);
}
```
```...
```