2022 The 4th C.Easy Counting Problem (EGF+NTT)

题意：give a charset,大小不超过10,第icharacters appear no less than ci,求字符串长度为n的方案数,至多300个询问,ci<=5000,n<=1e7
（Pictures are not copied,I don't know if the competition for money will be held==）
思路：指数生成函数
由egf定义,第k个字符的egf为$f(k)={\sum }_{c_k}^{+oo}\frac{x^i}{i!}$
则答案为$[\frac{x^n}{n!}]{\prod }_{k=1}^{w}f(k),w为字符集大小$
但是n比较大,It's definitely not possible to roll directly.改写一下f(k)的形式
$f(k)=exp(x)-{\sum }_{i=0}^{c_k-1}\frac{x^i}{i!}$
可以将exp(x)看成一个整体,The final answer is in the form
${\sum }_{i=0}^{w}g(i)\ast exp(x{)}^i={\sum }_{i=0}^{w}g(i)\ast exp(ix),其中g(i)是一个多项式$
g(i)The maximum number of times does not exceed$\sum c_i$,而exp(ix)Each coefficient of is known,Then just loop over eachg(i)The coefficient of the term is multiplied byexp(ix)Corresponding coefficients are sufficient.最后别忘了乘n!
The specific spelling can be used for referencedp的思路,设dpij表示前i个fThe formula obtained by multiplyingexp(jx)What is the coefficient of ,There is a polynomial
转移方程$d{p}_{i,j}=d{p}_{i-1,j}-d{p}_{i,j-1}\ast {\sum }_{k=0}^{c_i-1}\frac{x^k}{k!}$,In fact, it is just a simulation of polynomial violence,This way of thinking a little clearer.
复杂度$O(w^{2}slogs+qws),s=\sum ci$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define IOS ios::sync_with_stdio(false),cin.tie(nullptr) 
#define _for(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define _rep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define pii pair<int ,int >
#define pb(v) push_back(v)
#define all(v) v.begin(),v.end()
#define int long long
#define inf 0x3f3f3f3f
#define INF 0x7f7f7f7f7f7f7f7f
#define endl "\n"
#define fi first
#define se second
#define ls p<<1
#define rs p<<1|1
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define AC return 0
#define ldb long double
const int maxn = 6e6+10;
const int p = 998244353;
const int mod = 998244353;
int Pow(int x,int d){
    
    int tans = 1;
    if(d == 0)return 1%p;
    int a = Pow(x,d/2);
    tans = 1ll*a*a%p;
    if(d%2)tans = 1ll*tans*x%p;
    return tans%p;
}
typedef vector<int> Poly;//多项式定义
inline Poly  operator + (const Poly&A ,const Poly&B){
    
    Poly res (max(A.size(),B.size()),0);
    for(int i=0 ;i<max(A.size(),B.size()) ;i++){
    
        if( i < A.size() && i<B.size() ) res[i] = (A[i]+B[i])%mod;
        else if( i >= A.size() ){
    
            res[i] = B[i];
        }
        else res[i] = A[i];
    }
    return res;
}
inline Poly  operator - (const Poly&A ,const Poly&B){
    
    Poly res (max(A.size(),B.size()),0);
    for(int i=0 ;i<max(A.size(),B.size()) ;i++){
    
        if( i < A.size() && i<B.size() ) res[i] = (A[i]-B[i]+mod)%mod;
        else if( i >= A.size() ){
    
            res[i] = (mod-B[i])%mod;
        }
        else res[i] = A[i];
    }
    return res;
}
int F1[maxn],F2[maxn];
int rev[maxn];
void NTT(int * A,int lim,int opt) {
    
    int i, j, k, m, gn, g, tmp;
    for(int i = 0; i < lim; ++i)rev[i] = (i & 1)*(lim >> 1) + (rev[i >> 1] >> 1);
    for(i = 0; i < lim; ++i)if (rev[i] < i) swap(A[i], A[rev[i]]);
    for(m = 2; m <= lim; m <<= 1) {
    
        k = m >> 1;
        gn = Pow(3,(p - 1) / m);
        for(i = 0; i < lim; i += m) {
    
            g = 1;
            for (j = 0; j < k; ++j, g = 1ll * g * gn % p) {
    
                tmp = 1ll * A[i + j + k] * g % p;
                A[i + j + k] = (A[i + j] - tmp + p) % p;
                A[i + j] = (A[i + j] + tmp) % p;
            }
        }
    }
    if(opt == -1){
    
        reverse(A+1,A+lim);
        int inv = Pow(lim,p-2);
        for(i = 0; i < lim; ++i) A[i] = 1ll * A[i] * inv % p;
    }
}
Poly mul(const Poly & A,const Poly & B){
    
    int n = A.size(),m = B.size();
    int siz = n + m - 1;
    Poly C(siz);
    if(siz < 64){
    //小于等于64项直接暴力算
        for(int i = 0;i < n;i++){
    
            for(int j = 0;j < m;j++)C[i+j] = (C[i+j] + 1LL*A[i]*B[j]%p)%p;
        }
        return C;
    }
    int fsiz = 1;
    while(fsiz <= siz)fsiz *= 2;
    for(int i = 0;i < fsiz;i++)F1[i] = F2[i] = 0;
    for(int i = 0;i < n;i++)F1[i] = A[i];
    for(int i = 0;i < m;i++)F2[i] = B[i];
    NTT(F1,fsiz,1);
    NTT(F2,fsiz,1);
    for(int i = 0;i < fsiz;i++)F1[i] = 1ll*F1[i]*F2[i]%p;
    NTT(F1,fsiz,-1);
    for(int i = 0;i < siz;i++){
    
        C[i] = F1[i];
    }
    return C;
}
const int N = 5e5+10;
const int M = 1e7+5;
int W,n;
int c[11],fac[M],ni_f[M];
int mi[11][M];
Poly f[11][11];
ll qsm(int a,int b){
    
    a %= mod;
    ll ans=1,tmp=a;
    while( b ){
    
        if( b&1 ) ans = (ans * tmp)%mod;
        tmp = tmp * tmp%mod;
        b>>=1;
    }
    return ans;
}
void ini(){
    
    int mx = 1e7;
    fac[0]=1;
    _for(i,1,mx) fac[i] = fac[i-1]*i%mod;
    ni_f[mx] = qsm(fac[mx],mod-2);
    _rep(i,mx-1,0) ni_f[i] = ni_f[i+1]*(i+1)%mod;
}
int S;
void ff(Poly F){
    
    F.resize(min(S+1,(int)F.size()));
}
void solve(){
    
    f[1][1].resize(1,1);
    f[1][0].resize(c[1]+1,0);
    _for(i,0,c[1]-1){
    
        f[1][0][i] = (mod-ni_f[i])%mod;
    }
    _for(i,2,W){
    
        _for(j,0,i){
    
            Poly t (c[i]+1,0);
            _for(k,0,c[i]-1){
    
                t[k] = (mod-ni_f[k])%mod;
            }
            f[i][0] = mul(f[i-1][0],t);
            ff(f[i][0]);
            f[i][j] = (f[i-1][j-1] + mul(f[i-1][j],t));
            ff(f[i][j]);
        }
    }
}
int Q(int n){
    
    int ans=0;
    for(int i=0 ;i<=W ;i++){
    // exp(ix)
        int pw = qsm(i,n-min(n,(int)f[W][i].size()-1ll));
        for(int j=min(n,(int)f[W][i].size()-1ll) ;j>=0 ;j--){
    
            int t = n-j;
            if( j < min(n,(int)f[W][i].size()-1ll) ) pw = pw * i%mod;
            ans = (ans + f[W][i][j] * pw %mod*ni_f[t]%mod)%mod;
        }
    }
    return ans*fac[n]%mod;
}
signed main(){
    
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif 
    IOS;
    cin>>W;
    _for(i,1,W) cin>>c[i];
    S = accumulate(c+1,c+1+W,0ll);
    ini();
    solve();
    int q;cin>>q;
    while( q-- ){
    
        int x;cin>>x;
        int ans = Q(x);
        cout<<ans<<endl;
    }
    AC; 
}