#4618. 咕

题目描述

对于一个长度为 $A$ 的正整数序列$B$，定义其一个长度为 $C(0 < C le A)$ 的非空子序列为一个长度为 $C$ 的下标序列 $P[1 dots C]$ ，满足 $1 le P[1] < P[2] < cdots <P[C] le A$ 。子序列本身就是按照顺序把对应的元素拿出来： $B[P[1]] ~ B[P[2]] ~ cdots ~B[P[C]]$ 。

给定一个长度为 $N$ 的正整数序列 $S$ 和一个长度为 $M$ 的正整数序列 $T$，同时再给定一个有 $K$ 条边的有向图 $G$ 。

请你求出它们有多少个公共子序列，满足把子序列拿出来之后，对于任意相邻两个元素 $(a,b)$，满足在 $G$ 中存在一条有向边 $<a,b>$。

这里子序列不同，定义为下标位置不同（即序列 $P$ 不同）。

数据范围

$1 le N,M le 3000 ,0 le K le 10^6 ,forall 1 le i le N, 1 le S[i] le 10^9, forall 1 le i le M, 1 le T[i] le 10^9, 1 le s,t le 10^9$

题解

考场上应当想出来的题哭辽。

考虑 $dp$ ， $f_{i,j}$ 表示以 $s_i$ 和 $t_j$ 结尾的公共子序列的个数，考虑转移，那我们可以大概画个图，然后会发现它其实是由前面的一些列的 $dp$ 值转移过来，于是前缀和优化即可。

代码

#include <bits/stdc++.h>
#define _(d) while(d(isdigit(c=getchar())))
using namespace std;
int R(){char c;_(!);int x=c^48;_()x=(x<<3)+(x<<1)+(c^48);return x;}
const int N=3005,P=1e9+7;
int n,m,k,t,a[N],b[N],f[N],h[N],s[N],ans;
bool p[N<<1][N<<1];map<int,int>mp;
int X(int x){return x>=P?x-P:x;}
int main(){
    n=R();m=R();k=R();
    for (int i=1;i<=n;i++){
        a[i]=R();
        if (!mp.count(a[i]))
            mp[a[i]]=++t;a[i]=mp[a[i]];
    }
    for (int i=1;i<=m;i++){
        b[i]=R();
        if (!mp.count(b[i]))
            mp[b[i]]=++t;b[i]=mp[b[i]];
    }
    for (int i=1,x,y;i<=k;i++){
        x=R(),y=R();
        if (!mp.count(x) || !mp.count(y))
            continue;
        x=mp[x];y=mp[y];p[y][x]=1;
    }
    s[0]=1;
    for (int i=1;i<=t;i++) p[i][0]=1;
    for (int i=1;i<=n;i++){
        for (int j=0;j<=m;j++)
            if (p[a[i]][b[j]]) h[j]=X(h[j]+s[j]);
        for (int j=1;j<=m;j++) h[j]=X(h[j]+h[j-1]);
        for (int j=1;j<=m;j++)
            if (a[i]==b[j]) f[j]=X(f[j]+h[j-1]);
        for (int j=0;j<=m;j++) s[j]=X(s[j]+f[j]),f[j]=h[j]=0;
    }
    for (int j=1;j<=m;j++) ans=X(ans+s[j]);
    printf("%d
",ans);return 0;
}