[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; }
ディスカッション
コメント一覧
まだ、コメントがありません