没有特别难=_=
\(k\le 5\) ,一开始没看到。。有了这个条件肯定是枚举每一个红板,然后把方案数加起来。
一个图形的周长显然是 \(\text{红板长度+板子个数}\times 2\) ,小奥的套路,把边移到边界上即可。
接下去考虑怎么统计每一个红板的方案数。
白板的长度要严格小于红板长度,可以先把这部分白板提取出来。
想了一会就有思路了。
首先想到,如果左边的白板长度定了,右边白板的长度定了,那么方案唯一确定,因此不需要枚举位置,只需要看在哪一边即可。
如果这个长度的白板数量超过 \(2\) ,那么可以当做 \(2\) ,因为不可能有 \(3\) 块长度相同的白板出现在同一个合法的图形里。
所以白板可以分为两类:长度出现次数为 \(1\) 的和 \(>1\) 的。
想了想,混在一起不是很好算,没啥思路。
那就考虑把这两块拆开来算。即枚举有多少块属于第一类,多少块属于第二类。
设第一类共 \(x\) 块,第二类共 \(y\) 块。
第一类选 \(i\) 块的方案数:\(2^i\times \binom{x}{i}\) ,就是选出 \(i\) 块,然后枚举在左边还是右边。
第二类有点讨厌,因为可以选一块放左边,放右边,或者两块都选。后来想到,钦定一块板子,选它就放左边,选另一块同长度的就放右边,那么选 \(i\) 块的方案数就是 \(\binom{2y}{i}\)
注意到这里板子只会对周长的 板子个数
产生影响,那么直接把上面两个东西卷起来就能得到 对于一块红板选 i 块白板的方案数
懒得算空间,于是乱开,都往大了开就是了。。。
写这题又出离谱事件,NTT写挂怎么能过样例哦,样例又不小,离谱离谱离谱。。。
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mkp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define sz(v) (int)v.size()
typedef long long LL;
typedef long double db;
template<class T>bool ckmax(T&x,T y){return x<y?x=y,1:0;}
template<class T>bool ckmin(T&x,T y){return x>y?x=y,1:0;}
#define rep(i,x,y) for(int i=x,i##end=y;i<=i##end;++i)
#define per(i,x,y) for(int i=x,i##end=y;i>=i##end;--i)
inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return f?x:-x;
}
#define mod 998244353
const int N=600005;
int n,k,a[N],q,ans[N],cnt[N];
namespace math{
inline int qpow(int n,int k){int res=1;for(;k;k>>=1,n=1ll*n*n%mod)if(k&1)res=1ll*n*res%mod;return res;}
inline void fmod(int&x){x-=mod,x+=x>>31&mod;}
int pw2[N],fac[N],ifc[N],inv[N];
void initmath(const int&n=600000){
pw2[0]=1;for(int i=1;i<=n;++i)fmod(pw2[i]=pw2[i-1]<<1);
fac[0]=1;for(int i=1;i<=n;++i)fac[i]=1ll*i*fac[i-1]%mod;
ifc[n]=qpow(fac[n],mod-2);for(int i=n-1;i>=0;--i)ifc[i]=1ll*ifc[i+1]*(i+1)%mod;
inv[1]=1;for(int i=2;i<=n;++i)inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;
}
int binom(int n,int m){return n<m?0:1ll*fac[n]*ifc[m]%mod*ifc[n-m]%mod;}
}
namespace poly{
using math::qpow;
using math::fmod;
const int M=N<<2;
int lim,rev[M],lg;
void init_poly(const int&n){
for(lg=0,lim=1;lim<n;++lg,lim<<=1);
for(int i=0;i<lim;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1));
}
void NTT(int*a,int op){
for(int i=0;i<lim;++i)
if(i>rev[i])swap(a[i],a[rev[i]]);
const int g=op?3:math::inv[3];
for(int i=1;i<lim;i<<=1){
const int wn=qpow(g,(mod-1)/(i<<1));
for(int j=0;j<lim;j+=i<<1){
int w0=1;
for(int k=0;k<i;++k,w0=1ll*w0*wn%mod){
const int X=a[j+k],Y=1ll*w0*a[i+j+k]%mod;
fmod(a[j+k]=X+Y),fmod(a[i+j+k]=X-Y+mod);
}
}
}
if(op)return;int ilim=qpow(lim,mod-2);
for(int i=0;i<lim;++i)a[i]=1ll*a[i]*ilim%mod;
}
#define clr(a,n) memset(a,0,sizeof(int)*(n))
#define cpy(a,b,n) memcpy(a,b,sizeof(int)*(n))
void poly_mul(int*f,int*g,int*h,int n,int m){
static int A[M],B[M];init_poly(n+m);
cpy(A,f,n),clr(A+n,lim-n),NTT(A,1);
cpy(B,g,m),clr(B+m,lim-m),NTT(B,1);
for(int i=0;i<lim;++i)h[i]=1ll*A[i]*B[i]%mod;
NTT(h,0);
}
void solve(int up){
static int x,y,A[M],B[M];
x=y=0;
for(int i=1;i<up;++i)
if(cnt[i]==1)++x;
else if(cnt[i]>=2)++y;
y<<=1;
for(int i=0;i<=x;++i)A[i]=1ll*math::pw2[i]*math::binom(x,i)%mod;
for(int i=0;i<=y;++i)B[i]=math::binom(y,i);
poly_mul(A,B,A,x+1,y+1);
for(int i=0;i<=min(x+y,N-5);++i)fmod(ans[i+up+1]+=A[i]);
}
}
signed main(){
n=read(),k=read(),math::initmath();
for(int i=1;i<=n;++i)++cnt[a[i]=read()];
for(int i=1;i<=k;++i)poly::solve(read());
q=read();
for(int i=1;i<=q;++i)printf("%d\n",ans[read()>>1]);
return 0;
}