Thuật toán

Ta sẽ sử dụng thuật toán quy hoạch động cho bài này

Gọi $s_i$ là ký tự thứ $i$ của xâu đã cho $s$.

Gọi $f(i), g(i), h(i)$ lần lượt là số dãy con (như định nghĩa trong đề) bằng C, CO và COW của xâu $s_1s_2\ldots s_i$. Quy ước $f(0) =g(0) = h(0) = 0$. Từ định nghĩa này, ta thấy ta cần tính $h(n)$

Ta sẽ duyệt $i=1,2,\ldots,n$ theo thứ tự. Với mỗi $i$, ta sẽ tìm cách tính $f(i), g(i), h(i)$. Như vậy, kết hợp với $f(0)=g(0)=h(0)=0$, khi ta duyệt đến $i$, ta đã tính được $f(i-1), g(i-1), h(i-1)$. Với mỗi chữ cái, xét 3 TH:

TH1: $s_i$ là chữ cái C

Trong trường hợp này, ta có tổng cộng $f(i-1)$ dãy con C và chỉ có thêm 1 dãy con C chính là xâu $s_i$. Do đó, $f(i) = f(i-1) + 1$. $g(i)$ và $h(i)$ không có gì thay đổi so với $g(i-1), h(i-1)$

TH2: $s_i$ là chữ cái O

Ta có tổng cộng $g(i-1)$ dãy con CO từ xâu $s_1s_2\ldots s_{i-1}$. Với chữ cái O ở vị trí $i$, ta có thể ghép với $f(i-1)$ dãy con C từ vị trí $i-1$ trở về trước để tạo thành $f(i-1)$ dãy con CO nữa. Như vậy, tổng cộng ta có $g(i) = g(i-1) + f(i-1)$ dãy con CO trong xâu $s_1s_2\ldots s_i$

$f(i)$ và $h(i)$ không có gì thay đổi so với $f(i-1), h(i-1)$

TH3: $s_i$ là chữ cái W

Tương tự thì ta cũng có $h(i) = h(i-1) + g(i-1)$ và $f(i), g(i)$ không thay đổi so với $f(i-1), g(i-1)$

Code (C++)

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;

int n;
string s;
// Su dung long long de tranh tran so
long long f[N], g[N], h[N];

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    freopen("CWORD.inp","r",stdin);
    freopen("CWORD.out","w",stdout);
    // code here
    cin >> n;
    cin >> s;
    // 1-indexed
    s = ' ' + s;
    // Quy uoc
    f[0] = 0; g[0] = 0; h[0] = 0;
    for(int i=1;i<=n;i++){
        // Truong hop khong doi
        f[i] = f[i-1];
        g[i] = g[i-1];
        h[i] = h[i-1];
        if(s[i] == 'C'){
            f[i] = f[i-1] + 1;
        }else if(s[i] == 'O'){
            g[i] = g[i-1] + f[i-1];
        }else if(s[i] == 'W'){
            h[i] = h[i-1] + g[i-1];
        }
    }
    cout << h[n];
    return 0;
}