[C++知识库]ABC 211 _C-chokudai

ABC 211 _C-chokudai

Problem Statement

You are given a string S.
How many ways are there to choose and underline eight of its characters so that those characters read c, h, o, k, u, d, a, i from left to right?
Since the count can be enormous, print it modulo (10^9+7).
Constraints
8≤ |S| ≤10^5
S consists of lowercase English letters.

Sample Input

chokudaichokudaichokudai

Sample Output

45

思路：

C++代码

#include<iostream>
#include<string> 
using namespace std;
const long long mod = 1e9 + 7;
int cnt[8];
int main() {
  string s;
  cin >> s;
  for(int i=0;i<s.length();i++){
    if      (s[i] == 'c') cnt[0]++;
    else if (s[i] == 'h') cnt[1] = (cnt[1] + cnt[0]) % mod;
    else if (s[i] == 'o') cnt[2] = (cnt[2] + cnt[1]) % mod;
    else if (s[i] == 'k') cnt[3] = (cnt[3] + cnt[2]) % mod;
    else if (s[i] == 'u') cnt[4] = (cnt[4] + cnt[3]) % mod;
    else if (s[i] == 'd') cnt[5] = (cnt[5] + cnt[4]) % mod;
    else if (s[i] == 'a') cnt[6] = (cnt[6] + cnt[5]) % mod;
    else if (s[i] == 'i') cnt[7] = (cnt[7] + cnt[6]) % mod;
  }
  cout << cnt[7] << endl;
  return 0;
}

官方解答：

用 dp 来做的：

QwQ