XVI.CF1251F Red-White Fence

这题充分显现出了FFT~~工具人~~的本性。

对于这个奇奇怪怪的图形的周长，我们平移平移就能发现，它为\(\text{(红木板长度+总木板数量)}*2\)。有了这个结论，我们只需要枚举当前用的是哪块红木板（红木板数量\(\leq 5\)），再求出用各种总木板数量的方案数，求个和即可。

我们考虑如何求出用每种数量的木板的方案数。

考虑当所有白木板的长度都不相同时，任意一块木板，无论放在红木板左边还是右边，方案都是存在且唯一的。因此，放置\(i\)块白木板的方案就是：\(C_u^i*2^i\)。其中，\(u\)表示互不相同的白木板的数量。\(C_u^i\)意为选择\(i\)块木板，\(2^i\)意为这\(i\)块木板可以任意放在红木板左边或右边。

相反，如果所有长度都有一块以上的白木板呢？显然，在一个栅栏中，最多只能放两块相同长度的白木板，即左边一块，右边一块。\(3\)块及以上的相同长度木板和两块木板没有任何区别。设有\(v\)种长度种类的木板，则\(i\)块木板的答案为：\(C_{2v}^i\)，因为每个长度都可以选择左边放还是不放以及右边放还是不放，因此是\(2v\)。

现在两种情形都有，怎么办呢？

卷一块呀。

设\(f(i)=C_u^i*2^i\)，\(g(i)=C_{2v}^i\)。计算\(h=f*g\)，则这块红木板对于选\(i\)块木板的答案的贡献即为\(h(i)\)。

则最终询问的答案即为\(\sum\limits_{i=1}^mh_i(q)\)，其中\(q\)为询问对象。

代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
const int G=3;
const int lim=1<<20,lg=20;
int n,m,cnt[lim+10],s1[lim+10],s2[lim+10],f[lim+10],g[lim+10],res[lim+10],invlim,fac[lim+10],invfac[lim+10],rev[lim+10];
int ksm(int x,int y){
	int rt=1;
	for(;y;x=(1ll*x*x)%mod,y>>=1)if(y&1)rt=(1ll*rt*x)%mod;
	return rt;
}
void NTT(int *a,int tp){
	for(int i=0;i<lim;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
	for(int md=1;md<lim;md<<=1){
		int rt=ksm(G,(mod-1)/(md<<1));
		if(tp==-1)rt=ksm(rt,mod-2);
		for(int stp=md<<1,pos=0;pos<lim;pos+=stp){
			int w=1;
			for(int i=0;i<md;i++,w=(1ll*w*rt)%mod){
				int x=a[pos+i],y=(1ll*w*a[pos+md+i])%mod;
				a[pos+i]=(x+y)%mod;
				a[pos+md+i]=(x-y+mod)%mod;
			}
		}
	}
	if(tp==-1)for(int i=0;i<lim;i++)a[i]=(1ll*a[i]*invlim)%mod;
}
int C(int n,int m){
	if(m>n)return 0;
	return 1ll*fac[n]*invfac[m]%mod*invfac[n-m]%mod;
}
int main(){
	for(int i=0;i<lim;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1));
	fac[0]=invfac[0]=1;
	for(int i=1;i<lim;i++)fac[i]=(1ll*fac[i-1]*i)%mod;
	invfac[lim-1]=ksm(fac[lim-1],mod-2);
	for(int i=lim-2;i>=1;i--)invfac[i]=(1ll*invfac[i+1]*(i+1))%mod;
	invlim=ksm(lim,mod-2);
	scanf("%d%d",&n,&m);
	for(int i=1,x;i<=n;i++)scanf("%d",&x),cnt[x]++;
	for(int i=1;i<lim;i++)s1[i]=s1[i-1]+(cnt[i]==1),s2[i]=s2[i-1]+(cnt[i]>=2);
	for(int i=1,x,u,v;i<=m;i++){
		scanf("%d",&x),u=s1[x-1],v=s2[x-1];
		for(int j=0;j<lim;j++)f[j]=1ll*C(u,j)*ksm(2,j)%mod,g[j]=C(v*2,j);
		NTT(f,1),NTT(g,1);
		for(int j=0;j<lim;j++)f[j]=(1ll*f[j]*g[j])%mod;
		NTT(f,-1);
		for(int j=0;j<lim-x-1;j++)res[j+x+1]=(res[j+x+1]+f[j])%mod;
	}
	scanf("%d",&m);
	for(int i=1,x;i<=m;i++)scanf("%d",&x),printf("%d\n",res[x/2]);
	return 0;
}

CF1251F Red-White Fence

XVI.CF1251F Red-White Fence

推荐阅读