Submission #6012966


Source Code Expand

Copy
#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;
}

Submission Info

Submission Time
Task E - Common Subsequence
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 500
Code Size 1270 Byte
Status
Exec Time 321 ms
Memory 188800 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt, s4.txt, s5.txt
All 500 / 500 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, s1.txt, s2.txt, s3.txt, s4.txt, s5.txt
Case Name Status Exec Time Memory
01.txt 33 ms 127232 KB
02.txt 33 ms 127232 KB
03.txt 33 ms 127232 KB
04.txt 33 ms 127232 KB
05.txt 33 ms 127232 KB
06.txt 313 ms 188800 KB
07.txt 321 ms 188800 KB
08.txt 302 ms 186752 KB
09.txt 307 ms 188800 KB
10.txt 299 ms 186752 KB
11.txt 312 ms 186752 KB
12.txt 310 ms 186752 KB
13.txt 313 ms 186752 KB
14.txt 314 ms 186752 KB
15.txt 305 ms 186752 KB
16.txt 295 ms 186752 KB
17.txt 315 ms 188800 KB
18.txt 296 ms 186752 KB
19.txt 300 ms 186752 KB
20.txt 300 ms 186752 KB
21.txt 307 ms 188800 KB
22.txt 300 ms 188800 KB
23.txt 45 ms 143744 KB
24.txt 283 ms 186880 KB
25.txt 58 ms 188800 KB
26.txt 46 ms 129408 KB
27.txt 321 ms 188800 KB
28.txt 321 ms 188800 KB
s1.txt 33 ms 127232 KB
s2.txt 33 ms 127232 KB
s3.txt 33 ms 127232 KB
s4.txt 33 ms 127232 KB
s5.txt 33 ms 127232 KB