[Educational Codeforces Round 75]F.Red-White Fence(OGF)

[Educational——手把手教你如何计数系列·第三期]
[对不起，第二期被咕掉了，并且这篇也是补写的博客]

题面

[以后都直接放传送门好了…]
[传送门]

翻译

[洛谷传送门]

题解

首先感受一下惨状。

其实这题思路十分简单，只是我sb了用了个快速幂然后$O(n{\log }^{2}n)$就被卡爽了。
显然周长是个摆设，因为$k\le 5$，我们枚举中间红色板子的长度，那么选的板子的个数就是确定的。
然后我们考虑如何在红木板两边摆放白木板，考虑从大到小摆放，假设白木板两两不同的话，那么显然怎么放都可以，因此方案数为$C_n^k\times 2^k$。
然而有相同木板时就麻烦了，注意到相同木板最多放两个，考虑分类讨论dp。
定义$cn{t}_i$为当前长度木板有多少个。
$$f_{i,j}=\{\begin{array}{l}{f}_{i?1,j}+2\times f_{i?1,j?1}(cn{t}_i=1)\\ f_{i?1,j}+2\times f_{i?1,j?1}+f_{i?1,j?2}(cn{t}_i\ge 2)\end{array}$$
这东西可以用OGF优化，设$c={\sum }_{i=1}^n[cn{t}_i=1]$,$d={\sum }_{i=1}^n[cn{t}_i\ge 2]$。
有生成函数:$(2x+1{)}^c(x^2+2x+1{)}^d=(2x+1{)}^c(x+1{)}^{2d}$。
这时候千万别着急直接用快速幂了。
因为这个式子两边的系数是可以直接算出来的…
然后$NTT$一下就好了。
复杂度:$O(nk\log n)$。
（为什么neal julao用了个快速幂都只有1000ms，太没天理了…）

实现

#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<stack>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
#define MAXN 600000
#define MOD 998244353
#define LL long long
#define G 3
typedef int Ploy[MAXN+5];
inline int read(){
    register int x=0,F=1;char c=getchar();while(c<'0'||c>'9'){
    if(c=='-')F=-1;c=getchar();}while(c>='0'&&c<='9'){
    x=x*10+c-'0';c=getchar();}return x*F;
}
int inv[MAXN+5],p2[MAXN+5],fac[MAXN+5];
inline int fst_pow(int x,int y)
{
    register int res=1;while(y){
    if(y&1)res=((LL)x*res)%MOD;x=((LL)x*x)%MOD,y>>=1;}return res;
}
void prepare(){
    fac[0]=p2[0]=1;for(int i=1;i<=MAXN;i++)fac[i]=1LL*i*fac[i-1]%MOD,p2[i]=2LL*p2[i-1]%MOD;inv[MAXN]=fst_pow(fac[MAXN],MOD-2);for(int i=MAXN-1;i>=0;i--)inv[i]=1LL*inv[i+1]*(i+1)%MOD;
}
int Comb(int n,int m){
    if(m>n)return 0;return 1LL*fac[n]*(1LL*inv[n-m]*inv[m]%MOD)%MOD;
}
inline void NTT(Ploy &a,int n,int x)
{
    for(register int i=0,j=0;i<n;i++){
    if(i<j)swap(a[i],a[j]);register int k=n>>1;while(k&&(k&j))j^=k,k>>=1;j^=k;}for(register int i=1;i<n;i<<=1){
    register int gn=fst_pow(G,(MOD-1)/(i<<1)),g=1;if(x==-1)gn=fst_pow(gn,MOD-2);for(register int j=0;j<i;j++,g=(1LL*g*gn)%MOD)for(register int l=j,r=l+i;l<n;l+=(i<<1),r=l+i){
    register int tmp=(1LL*a[r]*g)%MOD;a[r]=(a[l]-tmp+MOD)%MOD;a[l]=(a[l]+tmp)%MOD;}}if(x==1)return ;register int ny=fst_pow(n,MOD-2);for(register int i=0;i<n;i++)a[i]=(1LL*a[i]*ny)%MOD;
}
inline void mod_Mul(Ploy &a,Ploy &b,Ploy &res,int n)
{
    static Ploy a0,b0;register int len=1;while(len<((n<<1)-1))len<<=1;copy(a,a+len,a0);copy(b,b+len,b0);NTT(a0,len,1),NTT(b0,len,1);for(register int i=0;i<len;i++)a0[i]=(1LL*a0[i]*b0[i])%MOD;NTT(a0,len,-1);copy(a0,a0+len,res);
}
int n,k,Q;
int a[MAXN+5],b[6];
int cnt1[MAXN+5],cnt2[MAXN+5],ans[6][MAXN+5];
int tmp[MAXN+5],f[MAXN+5],g[MAXN+5],res[MAXN+5];
inline void solve(int x){
    memset(f,0,sizeof(f));memset(g,0,sizeof(g));register int pos=lower_bound(a+1,a+n+1,b[x])-a;for(int i=0;i<n*2;i++)f[i]=1LL*Comb(cnt1[pos],i)*p2[i]%MOD,g[i]=Comb(cnt2[pos]*2,i);mod_Mul(f,g,ans[x],(n+1)/2+1);for(register int i=0;i<=n;i++)res[i+b[x]+1]=(res[i+b[x]+1]+ans[x][i])%MOD;
}
int main()
{
    prepare();n=read(),k=read();for(register int i=1;i<=n;i++)a[i]=read();for(register int i=1;i<=k;i++)b[i]=read();sort(a+1,a+n+1);for(register int i=1,j=1;i<=n;i=j){
    while(j<=n&&a[i]==a[j])j++;cnt1[j]=cnt1[i],cnt2[j]=cnt2[i];if(j-i==1)cnt1[j]++;else cnt2[j]++;}for(register int i=1;i<=k;i++)solve(i);Q=read();while(Q--){
    int x=read();printf("%d\n",res[x/2]);}
}