[AOJ] No. 0386 ワープ装置

問題

方針

\( d(i) \) を文字 \( i \) の出口への行き方の数として、動的計画法を行います。初期値は \( d(s_0) = 1\) とします。更新式は、\( d(s_i) \leftarrow d(s_i) + d(t_i) \ (1 \leq i \leq N – 2)\) です。\( i \) の範囲が \( N – 2 \) までなのは、\( d(s_{N-1}) \leftarrow d(s_{N-1}) + d(t_{N-1}) \) と更新してしまうと、星 \( N \) からさらにワープする場合の数を足してしまうからです。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll my_pow(ll x, ll n) {
    if (n == 0) return 1;
    if (n % 2 == 0) return my_pow(x * x, n / 2);
    return x * my_pow(x, n - 1);
}

int main() {
    int N;
    cin >> N;
    string s, t;
    cin >> s >> t;
    ll mod = my_pow(10, 9) + 7;
    ll d[N][26]{};
    d[0][s[0] - 'a'] = 1;
    for (int i = 1; i < N; i++) {
        for (int j = 0; j < 26; j++) {
            d[i][j] = d[i - 1][j];
        }
        d[i][s[i] - 'a'] += d[i][t[i] - 'a'];
        d[i][s[i] - 'a'] %= mod;
    }
    cout << d[N - 2][t[N - 1] - 'a'] << "\n";
    return 0;
}