ワープ装置 [パソコン甲子園2018 予選 G]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0386

考察過程

1. mod10^9+7なのでDP数え上げ感がある
2. dpをまず考えるが、制約を見ると「dp[i] := 星iにたどり着く組み合わせ数」っぽい
3. 更新はそれより前の星の今いる出口と同じ文字の入り口から遷移がある
4. これは集約しておくことができる
5. 解けた

解法

https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0386/judge/3162191/C++14

DPをする。
dp[i] := 星iにたどり着く組み合わせ数
遷移は、それより前の星の今いる出口と同じ文字の入り口からなので、同じ文字の入り口を集約しておこう。
sm[c] := 入り口の文字がcである星の組み合わせ数の総和
これを使って計算していこう。

int N;
string S, T;
mint dp[101010];
mint sm[26];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S >> T;

    dp[0] = 1;
    sm[S[0] - 'a'] = 1;

    rep(i, 1, N) {
        dp[i] = sm[T[i] - 'a'];
        sm[S[i] - 'a'] += dp[i];
    }

    cout << dp[N - 1] << endl;
}