Codeforces 1096G

给定车票的位数（ 是偶数）和 个可用的数字 。一张车票是“幸运的”，当且仅当它前位数字之和等于后位数字之和。求幸运车票的总数，结果对998244353取模。

数据范围：

分析

算法步骤：

• 构造初始多项式
• 使用NTT计算
• 遍历的系数计算取模即为最终答案

#include<bits/stdc++.h>
#define LL long long 
#define poly vector<LL>
using namespace std;
const int N=2e6+10;
int s[N];
LL fac[N],invfac[N];
const int mod=998244353;
LL qpow(LL b,LL p=mod-2){
    LL res=1;
    while(p){
        if(p&1) res=res*b%mod;
        p>>=1;
        b=b*b%mod;
    }
    return res;
}
namespace Poly {
    const LL mod=998244353;
    const LL g=3;
    const LL inv=332748118;
    int len,bit,ivlen,rev[N];
    inline void init(int l1,int l2){
        len=1; bit=0;
        while (len<=l1+l2) len<<=1,bit++;
        for (int i=0;i<len;i++){
            rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
        }
        ivlen=qpow(len);
    }
     
    inline void ntt(poly& f,int opt){
        for(int i=0;i<len;i++){
            if (i<rev[i]) swap(f[i],f[rev[i]]);
        }
        for (int mid=1;mid<len;mid<<=1){
            LL tmp=qpow(g,(mod-1)/(mid*2));
            if (opt==-1) tmp=qpow(tmp);
            for (int i=0;i<len;i+=mid*2){
                LL w=1;
                for (int j=0;j<mid;j++,w=w*tmp%mod){
                    LL x=f[i+j],y=w*f[i+j+mid]%mod;
                    f[i+j]=(x+y)%mod;
                    f[i+j+mid]=(x-y+mod)%mod;
                }
            }
        }
        if (opt==-1){
            for (int i=0;i<len;i++) f[i]=f[i]*ivlen%mod;
            while (*prev(f.end())==0) f.pop_back();
        }
    }
     
    inline void mul(poly& f,poly g){
        int lf=f.size(),lg=g.size();
        init(lf,lg);
        f.resize(len); g.resize(len);
        ntt(f,1); ntt(g,1);
        for (int i=0;i<len;i++) f[i]=f[i]*g[i]%mod;
        ntt(f,-1);
    }
};
int d[N];
poly dfs(int l,int r){
    if(l==r){
        poly tmp;
        tmp.resize(11,0);
        for(int i=0;i<10;i++) tmp[i]=d[i];
        return tmp;
    }
    int mid=(l+r)>>1;
    poly a1=dfs(l,mid);
    poly a2=dfs(mid+1,r);
    Poly::mul(a1,a2);
    return a1;
}
int main(){
    int n,k;
    cin>>n>>k;
    int m=(n>>1);
    for(int i=1;i<=k;i++){
        int x;cin>>x;
        d[x]=1;
    }
    poly ans=dfs(1,m);
    LL res=0;
    for(LL num:ans) res=(res+num*num)%mod;
    cout<<res<<'\n';
    return 0;
}

参考文章：https://mp.weixin.qq.com/s/O1W4bX9w8A8I1Ee9trGm9w