-
Notifications
You must be signed in to change notification settings - Fork 85
Expand file tree
/
Copy path008.cpp
More file actions
33 lines (29 loc) · 918 Bytes
/
008.cpp
File metadata and controls
33 lines (29 loc) · 918 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
using namespace std;
string S;
long long mod = 1000000007;
long long dp[100009][8];
int main() {
// Step #1. Input
int N;
cin >> N;
cin >> S;
// Step #2. Dynamic Programming (DP)
dp[0][0] = 1;
for (int i = 0; i < (int)S.size(); i++) {
for (int j = 0; j <= 7; j++) {
dp[i + 1][j] += dp[i][j];
if (S[i] == 'a' && j == 0) dp[i + 1][j + 1] += dp[i][j];
if (S[i] == 't' && j == 1) dp[i + 1][j + 1] += dp[i][j];
if (S[i] == 'c' && j == 2) dp[i + 1][j + 1] += dp[i][j];
if (S[i] == 'o' && j == 3) dp[i + 1][j + 1] += dp[i][j];
if (S[i] == 'd' && j == 4) dp[i + 1][j + 1] += dp[i][j];
if (S[i] == 'e' && j == 5) dp[i + 1][j + 1] += dp[i][j];
if (S[i] == 'r' && j == 6) dp[i + 1][j + 1] += dp[i][j];
}
for (int j = 0; j <= 7; j++) dp[i + 1][j] %= mod;
}
// Step #3. Output the answer
cout << dp[S.size()][7] << endl;
return 0;
}