或者说...

是这题:http://codeforces.com/gym/100959/attachments/download/4248/20152016-petrozavodsk-winter-training-camp-makoto-rng58-soejima-sontest-4-en.pdf

题意:感谢杨主力@FizzyDavid 的翻译!

给你俩排列

你要把它们"归并排序"一样归并起来(当然没有顺序) 问最后的序列有几种样子

我们考虑一个dp函数

我们考虑

如果我们安排了一个方案,放了前i个a数组的数字和j个b数组的数字

显然当a[i]!=b[j]的时候,我们可以发现

dp(i,j) = dp(i-1,j) + dp(i,j-1)

然而这个"显然"可能不太显然,所以我还是解释下吧..

对于前面(i-1,j)的排列,那么我们在后面加a[i]上去都是一种方案

对于前面(i,j-1)的排列,那么我们在后面加b[j]上去都是一种方案

所以dp(i,j) = dp(i-1,j) + dp(i,j-1)

然而问题来了

当a[i] == b[j]的时候这方法显然不行了,不然可能会有重复

我们就要计算它的重复个数

我们定义一个函数f(x),代表对于两个完全相同的排列而言,各放i个元素能组成的排列数

f(x)可以用前面的dp方法推出来,因为f(x) = dp(x,x-1) = dp(x-1,x) 因为在这情况下..俩完全相同的排列中dp(x,x-1)和dp(x-1,x)是等价的,所以任意一个排列的最后加一个x即可

那么

dp(i,j) = dp(i-1,j) + dp(i,j-1) - dp(i-k,j-k) * f(k-1) (a[i-k]~a[i] == b[j-k]~b[j] , k>0)

具体为啥我也不知道..本着sample过了大胆猜想不用证明的心态submit的

又到了感谢@FizzyDavid的时间

FizzyDavid带我证明出来了..

首先我们可以观察得到f数组就是卡特兰数.........

我们把它抽象成一堆()

我们可以发现

(()())可以代表着abacbc

就是说,第几个左括号代表第几个上面序列的字符,右括号同理

所以我们发现,当如果出现第一个合法序列的时候,即(()()),代表着一个部分,这一个部分有且仅有另外一种代表方式,也就是左右括号反过来

(因为第一个(之后,'('与')'已经可以确定的代表两个不同的字符)

合法括号序列的个数即为卡特兰数,也就是f数组(我:这也行...),正好把左右括号去掉以后的卡特兰数(我:.....好神奇啊)所以是f(k-1)

所以..就是这样了....

再次鸣谢@FizzyDavid 

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int dp[2005][2005];
int dps[2005][2005];
int last[2005][2005];
const int modo=1000000007;
int a[2005],b[2005];
int val[2005];
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n;
    scanf("%d",&n);
    dp[0][0]=1;
    int i,j;
    for (i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for (i=0;i<=n;i++)
    {
        for (j=0;j<=n;j++)
        {
            if ((i==j)&&(i!=0))
            {
                dp[i][j]-=dp[i][j-1];
                dp[i][j]+=modo;
                dp[i][j]%=modo;
                val[i]=dp[i][j];
            }
            dp[i+1][j]+=dp[i][j];
            dp[i+1][j]%=modo;
            dp[i][j+1]+=dp[i][j];
            dp[i][j+1]%=modo;
        }
    }
    val[0]=1;
    for (i=0;i<n;i++)
    {
        scanf("%d",&b[i]);
        dps[i][0]=1;
        dps[0][i]=1;
    }
    dps[0][n]=1;
    dps[n][0]=1;
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=n;j++)
        {
            if (a[i-1]==b[j-1])
            {
                last[i][j]=last[i-1][j-1]+1;
                dps[i][j]=dps[i-1][j]+dps[i][j-1];
                dps[i][j]%=modo;
                int k;
                for (k=1;k<=last[i][j];k++)
                {
                    dps[i][j]-=(long long)dps[i-k][j-k]*val[k-1]%modo;
                    dps[i][j]%=modo;
                }
                dps[i][j]+=modo;
                dps[i][j]%=modo;
            }
            else
            {
                last[i][j]=0;
                dps[i][j]=dps[i-1][j]+dps[i][j-1];
                dps[i][j]%=modo;
            }
        }
    }
    printf("%d\n",dps[n][n]);
    return 0;
}