Two
题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=5791
Description
Alice gets two sequences A and B. A easy problem comes. How many pair of sequence A' and sequence B' are same. For example, {1,2} and {1,2} are same. {1,2,4} and {1,4,2} are not same. A' is a subsequence of A. B' is a subsequence of B. The subsequnce can be not continuous. For example, {1,1,2} has 7 subsequences {1},{1},{2},{1,1},{1,2},{1,2},{1,1,2}. The answer can be very large. Output the answer mod 1000000007.
Input
The input contains multiple test cases.
For each test case, the first line cantains two integers N,M(1≤N,M≤1000). The next line contains N integers. The next line followed M integers. All integers are between 1 and 1000.
Output
For each test case, output the answer mod 1000000007.
Sample Input
3 2
1 2 3
2 1
3 2
1 2 3
1 2
Sample Output
2
3
Source
2016 Multi-University Training Contest 5
##题意:
求A和B中有多少对子集完全相同.
##题解:
动态规划.
dp[i][j]:分别处理到i\j时ai==bj且用上ai bj后的对数. (ai!=bj时dp=0)
前缀和优化:
sum[i][j]:分别处理到i\j时满足条件的子集对数. (不一定用上ai bj)
状态转移:
dp[i][j] = sum[i-1][j-1] + 1;
用上ai bj后的对数为i\j之前的任意子集对再加上(ai, bj)这对子集.
sum[i][j] = dp[i][j] + (sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1]);
前缀和由当前满足条件的对数 + 之前满足条件的对数而来(去重).
##代码:
``` cpp
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define eps 1e-8
#define maxn 1100
#define mod 1000000007
#define inf 0x3f3f3f3f
#define IN freopen("in.txt","r",stdin);
using namespace std;
int n, m;
int a[maxn];
int b[maxn];
LL dp[maxn][maxn];
LL sum[maxn][maxn];
int main(int argc, char const *argv[])
{
//IN;
//int t; cin >> t;
while(scanf("%d %d", &n,&m) != EOF)
{
for(int i=1; i<=n; i++) scanf("%d", &a[i]);
for(int i=1; i<=m; i++) scanf("%d", &b[i]);
memset(dp, 0, sizeof(dp));
memset(sum, 0, sizeof(sum));
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if(a[i] == b[j]) {
dp[i][j] = (sum[i-1][j-1] + 1LL) % mod;
}
sum[i][j] = (dp[i][j] + sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + mod) % mod;
}
}
LL ans = sum[n][m];
/*
for(int i=1; i<=n; i++) {
for(int j=1; j<=m; j++) {
if(a[i] == b[j])
ans = (ans + dp[i][j]) % mod;
}
}
*/
printf("%I64d\n", ans);
}
return 0;
}