A26405. 子序列
填空题
困难
知识点
题目描述
子序列
题目描述
给定两个整数序列，第一个序列长度为 n，第二个序列长度为 m。请问，这两个序列有多少种公共的子序列？输出数量模 998244353 的余数。
所谓子序列，是指从原序列中选择部分或全部元素组成新序列，这些元素在原序列中不必连续，但要保持在原序列中的顺序。只要下标不同，哪怕数字相同，也要算成不同的子序列。
输入格式
第一行：两个整数表示 n 与 m；
第二行： n 个数字 a1,a2,... ,an；
第三行：m 个数字 b1,b2,... ,bm；
输出格式
单个整数表示答案。
输入样例
4 3
3 4 6 2
3 3 2输出样例
6说明提示
1≤n,m≤2000 , 1≤ai,bj≤100,000
参考答案
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 998244353;
int main() {
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for (int i = 0; i < n; ++i) cin >> a[i];
for (int i = 0; i < m; ++i) cin >> b[i];
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
// 空子序列
for (int i = 0; i <= n; ++i) dp[i][0] = 1;
for (int j = 0; j <= m; ++j) dp[0][j] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (a[i-1] == b[j-1]) {
dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]) % MOD;
} else {
dp[i][j] = (dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]) % MOD;
}
if (dp[i][j] < 0) dp[i][j] += MOD;
}
}
cout << dp[n][m] << endl;
return 0;
}
上一题
下一题