自动搬运

查看原文

来自洛谷，原作者为

	Demeanor_Roy 小时候我们总想去改变别人，后来发现，比起改变，筛选是性价比更高的事。

搬运于2025-08-24 22:45:49，当前版本为作者最后更新于2023-12-14 14:01:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

• 原题链接。

我们将 $1 \sim w$ 中在 B 序列出现过的元素称作关键元素。

显然，对于一个可能产生贡献的选择方案，关键元素均不能选。于是我们记非关键元素的数量为 $c$。

将 A 序列中的关键元素按下标顺次提出来，得到下标序列 $p$。我们不妨对 $p$ 的每个长为 $m$ 的子串计算贡献。

当前子串能够产生贡献，当且仅当它与 B 序列完全相同。这一点可以用 kmp 进行判定。接下来我们需要考虑的是贡献系数。

对于子串 $p_i,p_{i+1},\dots,p_{i+m-1}$，显然区间 $[p_i,p_{i+m-1}]$ 内的非关键元素均需要被删除。 记其数量为 $o$。则该子串的贡献为 ${c-o} \choose {d-o}$。至于 $o$ 的维护，可以用双指针加桶实现。时间复杂度线性。

一个细节是，如果你 kmp 的写法会访问到 $B_{m+1}$，记得清空这个位置。否则只能通过后两个 Subtask。

代码：

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+10,mod=1e9+7;
int T,n,m,c,w,d,o,L,ans,a[N],b[N],p[N];
int nx[N],cnt[N],fct[N],inv[N],finv[N];
bool vis[N];
inline int read()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return x;
}
inline int C(int x,int y){return y<0||x<y?0:1ll*fct[x]*finv[y]%mod*finv[x-y]%mod;}
inline void clear()
{
	c=o=L=ans=0;a[n+1]=b[m+1]=0;
	for(int i=1;i<=w;i++) cnt[i]=vis[i]=0; 
}
int main()
{
	fct[0]=inv[0]=finv[0]=fct[1]=inv[1]=finv[1]=1;
	for(int i=2;i<N;i++)
	{
		fct[i]=1ll*fct[i-1]*i%mod;
		inv[i]=(mod-1ll*mod/i*inv[mod%i]%mod)%mod;
		finv[i]=1ll*finv[i-1]*inv[i]%mod;
	}
	T=read();
	while(T--)
	{
		n=read(),m=read(),w=read(),d=read();clear();
		for(int i=1;i<=n;i++) a[i]=read();
		for(int i=1;i<=m;i++) b[i]=read(),vis[b[i]]=true;
		for(int i=1;i<=w;i++) if(!vis[i]) ++c;
		for(int i=1;i<=n;i++) if(vis[a[i]]) p[++L]=i;
		for(int i=2,j=0;i<=m;i++)
		{
			while(j&&b[i]!=b[j+1]) j=nx[j];
			if(b[i]==b[j+1]) ++j;nx[i]=j;
		}
		for(int i=1,j=0,l=1,r=0;i<=L;i++)
		{
			while(r<p[i])
			{
				++r;
				if(vis[a[r]]) continue;
				++cnt[a[r]];if(cnt[a[r]]==1) ++o;
			}
			if(i>=m)
				while(l<p[i-m+1])
				{
					if(!vis[a[l]]) 
					{
						--cnt[a[l]];
						if(!cnt[a[l]]) --o;
					}
					l++;
				}
			while(j&&a[p[i]]!=b[j+1]) j=nx[j];
			if(a[p[i]]==b[j+1]) ++j;if(j==m) ans=(ans+C(c-o,d-o))%mod;
		}
		printf("%d\n",ans);	
	}
	return 0;
}