Submit Info #3048

Problem Lang User Status Time Memory
Number of Substrings cpp drken WA 92 ms 69.43 MiB

ケース詳細
Name Status Time Memory
all_same_00 WA 86 ms 68.70 MiB
all_same_01 WA 84 ms 69.02 MiB
all_same_02 WA 83 ms 69.06 MiB
all_same_03 WA 83 ms 68.93 MiB
all_same_04 WA 84 ms 68.66 MiB
example_00 WA 5 ms 0.56 MiB
example_01 WA 6 ms 0.57 MiB
example_02 WA 6 ms 0.55 MiB
example_03 WA 6 ms 0.59 MiB
fib_str_00 WA 87 ms 69.43 MiB
fib_str_01 WA 65 ms 50.99 MiB
fib_str_02 WA 62 ms 48.66 MiB
fib_str_03 WA 57 ms 44.66 MiB
fib_str_04 WA 85 ms 67.83 MiB
max_random_00 WA 89 ms 68.66 MiB
max_random_01 WA 91 ms 69.11 MiB
max_random_02 WA 92 ms 69.11 MiB
max_random_03 WA 91 ms 68.99 MiB
max_random_04 WA 90 ms 68.65 MiB
random_00 WA 74 ms 54.62 MiB
random_01 WA 86 ms 64.71 MiB
random_02 WA 15 ms 7.96 MiB
random_03 WA 79 ms 60.08 MiB
random_04 WA 57 ms 38.99 MiB

#include <iostream> #include <string> #include <vector> using namespace std; const int MOD = 1000000007; // res[i][c] := i 文字目以降で最初に文字 c が登場する index (存在しないときは n) vector<vector<int> > calcNext(const string &S) { int n = (int)S.size(); vector<vector<int> > res(n+1, vector<int>(26, n)); for (int i = n-1; i >= 0; --i) { for (int j = 0; j < 26; ++j) res[i][j] = res[i+1][j]; res[i][S[i]-'a'] = i; } return res; } // mod 1000000007 の世界で a += b する関数 void add(long long &a, long long b) { a += b; if (a >= MOD) a -= MOD; } int main() { // 入力 string S; cin >> S; int n = (int)S.size(); // 前処理配列 vector<vector<int> > next = calcNext(S); // DP vector<long long> dp(n+1, 0); dp[0] = 1; // 初期化、空文字列 "" に対応 for (int i = 0; i < n; ++i) { for (int j = 0; j < 26; ++j) { if (next[i][j] >= n) continue; // 次の文字 j がもうない場合はスルー add(dp[next[i][j] + 1], dp[i]); } } // 集計 long long res = 0; for (int i = 0; i <= n; ++i) add(res, dp[i]); cout << res << endl; }