首页 › 题库 › C/C++编程考级 › C/C++编程七级 › 简答题
简答题 偏难
#13159

子序列 题目描述 给定两个整数序列,第一个序列长度为 n,第二个序列长度为 m。请问,这两个序列有多少种公共的子序列?输出数量模 998244353 的余数。…

子序列

题目描述

给定两个整数序列,第一个序列长度为 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

限制

时间限制:1000ms

内存限制:512MiB

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; using namespace std; const int MOD = 998244353; int main() {     int n, m;     cin &gt;&gt; n &gt;&gt; m;     vector&lt;int&gt; a(n), b(m);     for (int i = 0; i &lt; n; ++i) cin &gt;&gt; a[i];     for (int i = 0; i &lt; m; ++i) cin &gt;&gt; b[i];          vector&lt;vector&lt;int&gt;&gt; dp(n + 1, vector&lt;int&gt;(m + 1, 0));          // 空子序列     for (int i = 0; i &lt;= n; ++i) dp[i][0] = 1;     for (int j = 0; j &lt;= m; ++j) dp[0][j] = 1;          for (int i = 1; i &lt;= n; ++i) {         for (int j = 1; j &lt;= 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] &lt; 0) dp[i][j] += MOD;         }     }          cout &lt;&lt; dp[n][m] &lt;&lt; endl;     return 0; }</pre>
这道题暂未补解析。