0386:

dp[i][j] = 星0?iの入り口jから入れる累計数として、動的計画法を行う。

string s, t;
// 略  
dp[0][s[0]-'a'] = 1;
for ( int i = 1; i < n; i++ ){
  dp[i][s[i]-'a'] = (dp[i][s[i]-'a'] + dp[i-1][t[i]-'a']) % M;
  for ( int j = 0; j < 26; j++ ) dp[i][j] = (dp[i][j] + dp[i-1][j]) % M;
}
// dp[n-2][t[n-1]-'a'] が答え

dp[i][j]はdp[j]に省略することが可能。

dp[s[0]-'a'] = 1;
for ( int i = 1; i < n-1; i++ ){
  dp[s[i]-'a'] = (dp[s[i]-'a'] + dp[t[i]-'a']) % M;
}
// dp[t[n-1]-'a'] が答え