提出 #6012966

---

ソースコード 拡げる

#include <bits/stdc++.h>

#define ll long long int
#define rep(i,a,n) for(ll i=(a); i<(n); i++)
#define chmin(x,y) {x = min(x,y); }
#define chmax(x,y) {x = max(x,y); }

using namespace std;

ll N, M, MOD=1000000007;
vector<ll> s(4000);
vector<ll> t(4000);

// dp[i][j]: i,j番目が部分共通文字列となるときの組み合わせ数
ll dp[4000][4000];

ll memo[4000][4000];

ll sum(ll i, ll j) {
	if (memo[i][j] != -1)
		return memo[i][j];
	ll res;
	if (i == 0 && j == 0) {
		res= dp[0][0];
	} else if (i == 0) {
		res = dp[0][j] + sum(0, j-1);
	} else if (j == 0) {
		res= dp[i][0] + sum(i-1, 0);
	} else {
		// res = dp[i][j] + sum(i-1, j) + sum(i, j-1) - sum(i-1, j-1);
		res = dp[i][j];
	        (res += sum(i-1, j)) %= MOD;
		(res += sum(i, j-1)) %= MOD;
		(res += MOD - sum(i-1,j-1)) %= MOD;
	}
	res %= MOD;
	return memo[i][j] = res;
}

signed main() {
	cin>>N>>M;
	rep(i,0,4000) rep(j,0,4000) memo[i][j]=-1;
	rep(i,1,N+1) cin>>s[i];
	rep(i,1,M+1) cin>>t[i];
	for (ll i=1; i<=N; i++)
		for (ll j=1; j<=M; j++) {
			if (s[i] == t[j]) {
				dp[i][j] = sum(i-1, j-1) + 1;
			} else {
				dp[i][j] = 0;
			}
			dp[i][j] %= MOD;
		}

	ll ans = 1 + sum(N, M);
	ans %= MOD;
	cout<<ans<<endl;
	return 0;
}

提出情報

ジャッジ結果