https://yukicoder.me/problems/no/762
前提知識
解法
https://yukicoder.me/submissions/307975
DPで解く。
dp[cu][t] := 頂点cuで終わり、PDCAのt番目まで正しく来ている組み合わせ
rep(cu, 0, N) if (S[cu] == T[0]) dp[cu][0] = 1;
これでdp[cu][0]の場合、Pの位置まで正しく来ているかカウント
rep(t, 1, 4) rep(cu, 0, N) { if (S[cu] == T[t]) fore(to, E[cu]) if (S[to] == T[t - 1]) dp[cu][t] += dp[to][t - 1]; }
これでdp[to][t-1]からdp[cu][t]への遷移で組み合わせ数をカウントする。
あとは、dp[cu][3]の総和が答え。
int N, M; string S; vector<int> E[101010]; mint dp[101010][4]; string T = "PDCA"; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M >> S; rep(i, 0, M) { int u, v; cin >> u >> v; u--; v--; E[u].push_back(v); E[v].push_back(u); } rep(cu, 0, N) if (S[cu] == T[0]) dp[cu][0] = 1; rep(t, 1, 4) rep(cu, 0, N) { if (S[cu] == T[t]) fore(to, E[cu]) if (S[to] == T[t - 1]) dp[cu][t] += dp[to][t - 1]; } mint ans = 0; rep(cu, 0, N) ans += dp[cu][3]; cout << ans << endl; }