咕

· · 个人记录

$f[i][j]=\sum_{k=1}^{i-1} \sum_{l=1}^{j-1}f[k][l]+1(a[i]==b[j],a[k]==b[l],<a[k],a[i]>)

//+1是因为可以只选a[i]和b[j]

//注意f[k][l]和+1是分开的

(讲台上没想起来，捂脸

然后g数组帮助i前缀和优化，sum为j转移的前缀和

这样就可以O(1)转移了

//此程序使用了qt专属名称，请勿模仿。侵权必究！！！
//我真是太菜了啊……
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3e3+10,M=6e3+10,P=1e9+7;
int n,m,k,cnt=0,a[N],b[N],c[M];
int f[N][N],g[N],ans=0;
bool v[N][N];
inline int read()
{
    int sum=0,flag=1; char c;
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') flag=-1;
    for(;c>='0'&&c<='9';c=getchar()) sum=(sum<<3)+(sum<<1)+c-'0';
    return sum*flag;
} 
int main()
{
    // freopen("gu.in","r",stdin);
    // freopen("gu.out","w",stdout);
    n=read(); m=read(); k=read();
    for(int i=1;i<=n;++i) a[i]=read(),c[++cnt]=a[i];
    for(int i=1;i<=m;++i) b[i]=read(),c[++cnt]=b[i];
    sort(c+1,c+cnt+1);
    cnt=unique(c+1,c+cnt+1)-c-1;
    for(int i=1;i<=n;++i) a[i]=lower_bound(c+1,c+cnt+1,a[i])-c;
    for(int i=1;i<=m;++i) b[i]=lower_bound(c+1,c+cnt+1,b[i])-c;
    for(int i=1;i<=k;++i)
    {
        int x=read(),y=read(),px,py;
        px=lower_bound(c+1,c+cnt+1,x)-c,py=lower_bound(c+1,c+cnt+1,y)-c;
        v[px][py]|=(c[px]==x&&c[py]==y);
    }
    for(int i=1;i<=n;++i)
    {
        ll sum=0;
        for(int j=1;j<=m;++j)
        {
            if(a[i]==b[j])
            {
                f[i][j]=(sum+1)%P;
                ans=(ans+f[i][j])%P;
            }
            if(v[b[j]][a[i]]) sum=(sum+g[j])%P;
            g[j]=(g[j]+f[i][j])%P;
        }
    }
    printf("%d\n",ans);
    return 0;
}
//试图加一点优化但是还是6000ms+

非正式博客，挂两天就匿了