多项式学习 Day 3.

第一篇多项式题解 >_<

思路

注意到周长其实就是红板长度加上选的板子的数量。

于是当我们确定了红板长度 \(L\) 和周长 \(C\) 之后，我们需要取出 \(\frac{C}{2}-L-1\) 块白板。

然后很恶心的是虽然板子不能一样长，但是可以在红板两侧各来一块相同长度的白板。

于是我们发现一种颜色的白板超过两条和两条是等价的。

然后我们考虑两种特殊情况：

• 所有白板都只有一条。

这种情况下，我们可以先选 \(j\) 条，然后分别考虑每条放左边还是右边。

如果从 \(i\) 种白板中选出 \(j\) 条，那么有 \(2^j\binom{i}{j}\) 种方案。

• 所有白板都有两条。

我们让第一条代表放在左边，第二条代表放在右边。

那么一种方案和选 \(j\) 条板子是一一对应的。

那么如果从 \(i\) 种白板种选出 \(j\) 条，那么有 \(\binom{2i}{j}\) 种方案。

然后我们发现选出 \(i\) 条白板的过程可以拆解成选出 \(j\) 条只有一条的白板和 \(i-j\) 条有两条的白板。

于是我们只需要把两部分拆开即可，先算出选出 \(j\) 条只有一条的白板和有两条的白板的方案数，然后卷积即可。

注意到白板的长度要小于红板，所以要对于每块红版单独 \(\text{NTT}\) 一次。

代码

//zhoukangyang AK IOI!
#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
const long long p=998244353;
long long qp(long long x,int y)
{
    long long res=1;
    for(long long now=x; y; now=now*now%p,y>>=1) if(y&1) res=res*now%p;
    return res;
}
long long A[6000003],B[6000003];
int rev[6000003],N=1;
void init()
{
    int d=N>>1;
    rev[0]=0,rev[1]=N>>1;
    for(int i=2; i<=N; i<<=1)
    {
        d>>=1;
        for(int j=0; j<i; ++j) rev[i+j]=rev[j]|d;
    }
    return ;
}
void NTT(long long* F,int op)
{
    for(int i=0; i<N; ++i) if(rev[i]>i) swap(F[i],F[rev[i]]);
    for(int len=2,M=1; len<=N; len<<=1,M<<=1)
    {
        long long w=qp(op?3:332748118,998244352/len);
        //omega(m,1)
        for(int l=0,r=len-1; l<=N; l+=len,r+=len)
        {
            long long w0=1;
            for(int i=l; i<l+M; ++i)
            {
                long long x=(F[i]+w0*F[i+M]%p)%p,y=(F[i]+p-w0*F[i+M]%p)%p;
                F[i]=x,F[i+M]=y,w0=w0*w%p;
            }
        }
    }
}
int cnt[1000003],b[13],q[1000003];
long long ans[1000003];
int t;
void solve(int lim)
{
	int P=0,Q=0;
	for(int i=1; i<lim; ++i) if(cnt[i]==1) ++P; else if(cnt[i]>=2) ++Q;
	Q<<=1;
	for(;N<=P+Q;N<<=1);
	for(int i=0; i<N; ++i) A[i]=B[i]=0;
	long long fz=1,fm=1;
    for(int i=0; i<=P; ++i,fz=fz*(P+1-i)%p,fm=fm*i%p) A[i]=fz*qp(fm,p-2)%p*qp(2,i)%p;
    fz=fm=1;
    for(int i=0; i<=Q; ++i,fz=fz*(Q+1-i)%p,fm=fm*i%p) B[i]=fz*qp(fm,p-2)%p;
    init();
    NTT(A,1),NTT(B,1);
    for(int i=0; i<N; ++i) A[i]=A[i]*B[i]%p;
    NTT(A,0);
    long long inv=qp(N,998244351);
    for(int i=0; i<N; ++i) A[i]=A[i]*inv%p;
    for(int j=1; j<=t; ++j) if(q[j]-lim>=0) ans[j]=(ans[j]+A[q[j]-lim])%p;
    return ;
}
signed main()
{
    int n=read(),k=read();
    for(int i=1; i<=n; ++i) ++cnt[read()];
    for(int i=1; i<=k; ++i) b[i]=read();
    t=read();
    for(int i=1; i<=t; ++i) q[i]=(read()>>1)-1;
    for(int i=1; i<=k; ++i) solve(b[i]);
	for(int i=1; i<=t; ++i) printf("%lld\n",ans[i]);
	return 0;
}