题解：AT_arc053_d [ARC053D] 2 つの山札

· · 题解

更好的阅读体验

打模拟赛被这个题伏击了，于是决定记录一下。

首先进行一个转化：建一个 n \times n 的网格图，对于第 i 行第 j 列的点 (i, j)，和 (i+1, j) 的连边上写着 b_j，和 (i, j+1) 的连边上写着 a_i。从 editorial 上面偷了一个图，表示 a = (3, 1, 4, 2, 5), b = (3, 2, 4, 1, 5) 的情形。

我们要求的，就是 (1, 1) \to (n, n)，只能往右走或往下走，本质不同的经过边上的数字序列个数。

我们考虑 f_{i, j} 表示 (1, 1) \to (i, j) 本质不同的路径数量。如果没有本质不同的限制，那么转移就是 f_{i, j} = f_{i-1, j} + f_{i, j-1}。

但是 f_{i-1, j} 和 f_{i, j-1} 中可能有重复的。我们假设这部分中重复的方案数是 g_{i, j}。那么最后的方程是

f_{i, j} = f_{i-1, j} + f_{i, j-1} - g_{i, j}

显然 a_i \not = b_j 的时候，我们从 (i-1, j) \to (i, j) 和 (i, j-1) \to (i, j) 走过的边上经过的数字是不同的，所以 g_{i, j} = 0。

接下来考虑 a_i = b_j 怎么办。

我们考虑两条重复的路径是怎么样。我们枚举这两条路径最后一次相交的位置 (p, q)。由于我们计算的是合并 \boldsymbol{f_{i-1, j}, f_{i, j-1}} 时多产生的重复路径数量，因此从 (1, 1) \to (p, q) 的这一段是没有重复的，所以方案数就是去重后的方案数 f_{p, q}。

接下来考虑 (p, q) \to (i, j) 的路径有什么性质。

我们发现，这两条路径一定会同时转向。

考虑反证。如果存在一个地方两条路径不同时转向，那么就会有两条路径在某一个时刻是平行的；由于 a, b 是 1 \sim n 的排列，所以所有平行的边上的数字互不相等。所以这两条路径不可能本质相同。

由这个观察我们进一步发现，这两条路径一定关于一条斜率为 1 的直线对称，也就是 i - p = j - q。同时由于我们钦定 (p, q) 是最后一次相交的位置，所以这两条路径除了端点处，和 (p, q), (i, j) 连线不交。

我们再考虑这条路径在什么时候可以转向。显然只有满足 a_i = b_j 的时候可以转向。因为要求转向后两条路径仍然相等。

我们把转向的点延长到那条直线上，与直线的交点 (x, y) 一定满足 a_x = b_y，即图中五角星处。

由此每条和这条直线不交的路径都对应着一条与其本质相同的，关于这条直线对称的路径。我们只对其中一条计数，就可以计算出重复的数量 g_{x, y}。

由上图中的五角星，我们可以得到转向的最大次数。我们假设 (p, q) 和 (i, j) 之间有 t 个 a_x = b_y 的 (x, y)（不包括 (i, j)）。把转向的位置离散化一下，就变成原点走到 (t, t)，不碰到 y = x 的方案数。用反射容斥或由卡特兰数定义平移一下，可以得到方案数为 C(t-1)，其中 C 是卡特兰数。

所以当 a_i = b_j，

g_{i, j} = \sum_{k = 1}^{min(i, j) - 1}[a_{i - k} = b_{j - k}]f_{i-k, j-k} C(t_k) t_k = \sum_{p = 1}^{k} [a_{i - p} = b_{j - p}]

看起来是 O(n^3) 的。但是别忘了，由于 a, b 是排列，所以 a_i = b_j 只有 O(n) 对。我们算 g_{i, j} 是 O(n) 的，所以问题在 O(n^2) 的时间内得到解决。

#include<bits/stdc++.h>
#define endl '\n'
#define N 2006
#define MOD 1000000007
using namespace std;
inline void add(int &x,int y) {x+=y,x-=x>=MOD?MOD:0;}
inline void dec(int &x,int y) {x+=MOD-y,x-=x>=MOD?MOD:0;}
int n,a[N],b[N],fac[N],ifac[N],f[N][N];
inline int qpow(int x,int y=MOD-2)
{
    int ret=1;
    for(;y;y>>=1,x=1ll*x*x%MOD)if(y&1)ret=1ll*ret*x%MOD;
    return ret;
}
void init()
{
    fac[0]=1;
    for(int i=1;i<N;i++)fac[i]=1ll*i*fac[i-1]%MOD;
    ifac[N-1]=qpow(fac[N-1]);
    for(int i=N-2;~i;i--)ifac[i]=1ll*(i+1)*ifac[i+1]%MOD;
}
inline int binom(int x,int y) {return x<y?0:1ll*fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;}
inline int cat(int x) {return (binom(2*x,x)-binom(2*x,x-1)+MOD)%MOD;}
main()
{
    scanf("%d",&n),init(),f[1][1]=1;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)if(i!=1||j!=1)
    {
        f[i][j]=(f[i-1][j]+f[i][j-1])%MOD;
        if(a[i]!=b[j])continue;
        for(int k=1,cnt=0;k<min(i,j);k++)
            if(a[i-k]==b[j-k])cnt++,dec(f[i][j],1ll*f[i-k][j-k]*cat(cnt-1)%MOD);
    }
    printf("%d\n",f[n][n]);
    return 0;
}