rt

#1,9,18,19 WA

#7,8,10,16,17,20 TLE

其它AC。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,m,w,de,mod=1e9+7,gj=0,now=0,ans,mps[1000005];
bool mp[1000005];
struct node
{
	int u,wz;
}c[1000005];
int a[1000005],b[1000005],nex[1000005],jc[1000005];
int ksm(int x,int y)
{
	int now=1;
	while(y!=0)
	{
		if(y%2==1)
		{
			now*=x;
			now%=mod;
		}
		x*=x;
		x%=mod;
		y/=2;
	}
	return now;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	jc[0]=1;
	for(int i=1;i<=1000000;i++)
	{
		jc[i]=jc[i-1]*i;
		jc[i]%=mod;
	}
	cin>>t;
	while(t--)
	{
		cin>>n>>m>>w>>de;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
		}
		for(int i=1;i<=m;i++)
		{
			cin>>b[i];
			if(mp[b[i]]==0)
			{
				gj++;
			}
			mp[b[i]]=1;
		}
		for(int i=1;i<=n;i++)
		{
			if(mp[a[i]]==1)
			{
				now++;
				c[now].u=a[i];
				c[now].wz=i;
			}
		}
		nex[1]=1;
		for(int i=2;i<=m;i++)
		{
			int j=nex[i-1];
			while(j>1&&b[i]!=b[j])
			{
				j=nex[j-1];
			}
			if(b[i]==b[j])
			{
				j++;
			}
			nex[i]=j;
		}
		int d=0,l=1,r=1,ns=0;
		for(int i=1;i<=now;i++)
		{
			d++;
			while(d>1&&c[i].u!=b[d])
			{
				d=nex[d];
			}
			if(c[i].u==b[d])
			{
				if(d==m)
				{
					for(r;r<=c[i].wz;r++)
					{
						if(mp[a[r]]==0)
						{
							mps[a[r]]++;
							if(mps[a[r]]==1)
							{
								ns++;
							}
						}
					}
					for(l;l<c[i-m+1].wz;l++)
					{
						if(mp[a[l]]==0)
						{
							mps[a[l]]--;
							if(mps[a[l]]==0)
							{
								ns--;
							}
						}
					}
					if(ns<=de)
					{
						int x=w-ns-gj,y=de-ns,z=x-y;
						ans=(ans+((jc[x]*ksm(jc[y],mod-2))%mod)*ksm(jc[z],mod-2)%mod)%mod;
					}
					d=nex[d]-1;
				}
			}
			else
			{
				d=1;
			}
		}
		cout<<ans<<'\n';
		for(int i=1;i<=max(n,max(m,w));i++)
		{
			mp[i]=0;
			mps[i]=0;
			a[i]=0;
			b[i]=0;
			nex[i]=0;
			c[i].u=0;
			c[i].wz=0;
		}
		ans=0;
		gj=0;
		now=0;
	}
	return 0;
}