2019年6月16日開催のAtCoder Beginner Contest 130 (ABC130)に参加した．E問題の解答例と解説．コンテスト時間中はD問題を時間ギリギリに解いて終了したため，後日，このE問題にも取り組んで見た．自力でACできなかったが，公式のPDF解説をヒントに自分の方針で最後まで解いてみた．

E - Common Subsequence (500点)

問題文はこちら．与えられた２つの整数列S(長さN), T(長さM)からそれぞれ部分列を取り出し，それらが一致する場合の数を10^9+7で割ったあまりを求める問題．ABC130 D問題 とは異なり，部分列は連続していなくてもよいためかなり大変そう．

方針: DP(動的計画法)

DPかな〜とは思ったものの，自力で漸化式を立てることができなかったため，公式PDF解説をヒントに漸化式を立てた．公式PDF解説の方針・漸化式とはやや異なっていることに注意する．

さて，整数列Sを i 項目(i<=N), Tを j 項目(j<=M)まで考慮した時の，部分列が一致する場合の数を sum[i][j] とする．ただしここでは，部分列の要素は1個以上とする．求める答えは sum[N][M] + 1 になる．(最後の+1はS, Tからともに要素0個の部分列を取り出したケース)
このsum[i][j]の定義は公式PDF解説に合わせてある．

漸化式

sum[i][j] を sum[x][y] (x<i, y<j) の式(漸化式)でかければ，i, j が小さいsum[i][j]から順次計算することで，sum[N][M]を求めることができる．
sum[i][j] は S,Tをそれぞれi, j 項目まで考慮した時の場合の数なので，
(S,Tをそれぞれi, j 項目まで考慮した時の場合の数)
 　= (i-1, j 項目までの場合の数(Siは使わない))
 　　　+ (i, j-1 項目までの場合の数(Tjは使わない))
　 　　- (i-1, j-1 項目までの場合の数(SiもTjも使わない))
 　　　+ (i, j 項目まででSiとTjは必ず使う場合の数)
つまり
sum[i][j]
 　= sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]
 　　　+ (i, j 項目まででSiとTjは必ず使う場合の数)
となる．

あとは，(i, j 項目まででSiとTjは必ず使う場合の数)を考える．
Si=Tjならのとき， i, j 項目まででSiとTjは必ず使うような一致するの部分列は，(i-1, j-1 項目まで考慮した時の一致する部分列の末尾に，Si, Tjをくっつけたものなので，
　(i, j 項目まででSiとTjは必ず使う場合の数) = sum[i-1][j-1] + 1
+1は，部分列の要素がそれぞれSi, Tj 1個だけの場合である．
Si ≠ Tj の時は， i, j 項目まででSiとTjは必ず使うような部分列は一致しないので，
　(i, j 項目まででSiとTjは必ず使う場合の数) = 0
以上をまとめると漸化式は，
Si = Tj のとき
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] +(sum[i-1][j-1] + 1)
Si ≠ Tj のとき
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]
となる．

なお，(i, j 項目まででSiとTjは必ず使う場合の数)は公式PDF解説のdp[i][j]と同じである．

初期条件

i=0 または j=0のとき，一方の部分列は要素0個の部分列にしかならず，sum[][]では要素0個の部分列をカウントしないことに注意すると
sum[i][j] = 0 (i=0 または j=0)

実装例

C++ による実装例は以下のようになる．(#include は省略)
10^9+7で割った余りを取りながら計算することに注意

#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;

int main() {
 const ll mod = 1000000007;
 int N, M;
 cin >> N >> M;
 vector<int> S(N), T(M);
 rep(i, N) cin >> S[i];
 rep(i, M) cin >> T[i];
 
 vector<vector<ll>> sum(N+1, vector<ll>(M+1, 0));
 // sum[i][j]: N=i, M=jの時の答え ただし，()は除く
 
 // 初期条件を満たす形で初期化済み
 
 for(int i=1; i<N+1; i++) {
   for(int j=1; j<M+1; j++) {
     // sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1] + dp[i][j]
     // dp[i][j] は S[i-1]==T[j-1] の時 = sum[i-1][j-1]+1, else 0
     sum[i][j] = (sum[i-1][j] + sum[i][j-1])%mod;
     sum[i][j] %= mod;
     sum[i][j] -= sum[i-1][j-1];
     sum[i][j] %= mod;
     if(S[i-1]==T[j-1]) {
       sum[i][j] += (sum[i-1][j-1]+1)%mod;
       sum[i][j] %= mod;
     }
   }
 }
 
 ll res = (sum[N][M]+1)%mod; // 除外していた()を加えて答え
 if(res<0) res += mod; // res < 0 の場合 modを足す
 cout << res << endl;
 
 return 0;
}

別解: sumに要素0の部分列を含めるケース

sum[i][j]に要素0個の部分列を含めるほうが自然な発想に思えたので，そのような別解を作成した．下の実装では要素0個の部分列を含めるときの場合の数をans[i][j]と定義している．基本的には元の実装と同じだが，Si=Tj時の
(i, j 項目まででSiとTjは必ず使う場合の数) を計算する時に+1が必要ないこと，初期条件がans[i][j]=1 (i=0またはj=0)であることに注意する．

#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef long long ll;

int main() {
 const ll mod = 1000000007;
 int N, M;
 cin >> N >> M;
 vector<int> S(N), T(M);
 rep(i, N) cin >> S[i];
 rep(i, M) cin >> T[i];
 
 // 別解
 vector<vector<ll>> ans(N+1, vector<ll>(M+1, 1));
 // ans[i][j]: N=i, M=jの時の答え ()も含む, ans[i][j] = sum[i][j] +1
 // 初期条件を満たす形で初期化済み
 
 for(int i=1; i<N+1; i++) {
   for(int j=1; j<M+1; j++) {
     // ans[i][j] = ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1] + dp[i][j]
     // dp[i][j] は S[i-1]==T[j-1] の時 = ans[i-1][j-1], else 0
     ans[i][j] = (ans[i-1][j] + ans[i][j-1])%mod;
     ans[i][j] %= mod;
     ans[i][j] -= ans[i-1][j-1];
     ans[i][j] %= mod;
     if(S[i-1]==T[j-1]) {
       ans[i][j] += ans[i-1][j-1]%mod;
       ans[i][j] %= mod;
     }
   }
 }
 
 ll res = ans[N][M];
 if(res<0) res += mod;
 cout << ans[N][M] << endl;
 
 return 0;
}