内存:128  时间:1

题目描述

    Zp幸运的得到了两个序列A和B,现在Zp想知道数列A和数列B的非空子数列有多少对是相同的。例如,{1,2}和{1,2}是相同的,而{1,2,4}和{1,4,2}是不同的。子序列可以是不连续的,例如,{1,1,2}有7个非空子序列{1},{1},{2},{1,1},{1,2},{1,2},{1,1,2}。最后的结果可能非常大,输出答案mod 1000000007。

输入

输入包含多组数据。
对于每组数据:
第一行包含两个整数N,M(1≤N,M≤1000);
第二行有N个整数,表示第一个数列;
第三行有M个整数,表示第二个数列。
所有的数字的取值范围为[1,1000]。

输出

输出对1000000007取模后的结果。

样例输入

3 2
1 2 3
2 1
3 2
1 2 3
1 2

样例输出

2
3

提示

多组测试数据的输入方法:

whlie(cin>>n>>m)

{

}

或者

while(scanf("%d%d",&n,&m)!=EOF)

{

}

代码如下

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e3+7;
const int mod =  1000000007;
int a[maxn];
int b[maxn];
long long dp[maxn][maxn];
int main()
{
   // freopen("in.txt", "r", stdin);
   // freopen("out.txt", "w", stdout);

    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        for(int i=1; i<=n; ++i)scanf("%d",&a[i]);
        for(int i=1; i<=m; ++i)scanf("%d",&b[i]);
        for(int i=1; i<=n; ++i)
        {
            for(int j=1; j<=m; ++j)
            {

                if(a[i]==b[j])
                    dp[i][j]=(dp[i-1][j]+dp[i][j-1]+1)%mod;
                else
                    dp[i][j]=(dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+mod)%mod;
            }
        }
        cout<<dp[n][m]<<endl;

    }
    /*
    srand((unsigned)time(NULL));
    for(int i=0; i<1000; ++i)
        cout<<rand()%1000<<' ';
    cout<<endl;
    for(int i=0; i<1000; ++i)
        cout<<rand()%1000<<' ';
    cout<<endl;
    return 0;
    */
}

代码来源于互联网,仅供参考!