A. Math Ball

题意

给定n个不同的小球，每种小球都有无穷多个，第i个小球有一个权值 $c_{i}$ ，现在你要从中选出不超过W个小球，定义其选择的权值为 $\sum_{k_{1}+k_{2}....k_{n}<=W}\prod_{i=1}^{n}k_{i}^{c_{i}}$ ,问所有选择方案的权值之和.

解析

考虑 $f_{i}(x)=\sum_{j=0}^{\infin}j^{c_{i}}x^{j}$ ,则原式变为 $\sum_{i=0}^{W}[x^{i}]\prod_{j=1}^{n}f_{j}(x)$ ,乘上个 $\frac{1}{1-x}$ 求个前缀和则变为 $[x^{W}]\frac{1}{1-x}\prod_{j=1}^{n}f_{j}(x)$ ，现在我们考虑如何处理 $f_{i}(x)$

考虑将自然数幂和展开 $i^{k}=\sum_{j=0}^{i}{k\brace j}j!{\binom{i}{j}}$

则 $f_{i}(x)=\sum_{j=0}^{\infin}x^{j}\sum_{k=0}^{j}{c_{i}\brace k}k!{\binom{j}{k}}=\sum_{k=0}^{\infin}{c_{i}\brace k}k!\sum_{j=k}^{\infin}x^{j}{\binom{j}{k}}$

而我们知道 $\sum_{j=k}^{\infin}x^{j}{\binom{j}{k}}=\frac{x^{k}}{(1-x)^{k+1}}$

所以原式可以转化为 $f_{i}(x)=\sum_{k=0}^{c_{i}}{c_{i}\brace k}k!\frac{x^{k}}{(1-x)^{k+1}}$

我们发现由于 $\sum_{i=1}^{n}c_{i}<=10^{5}$ ，所以 ${c_{i}\brace k}$ 可以直接第二类斯特林数行就行了

我们设 $g(x)=\frac{x}{1-x}$ ,则 $f_{i}(x)= \frac{1}{1-x}\sum_{k=0}^{c_{i}}{c_{i}\brace k}k!g(x)^{k}$

所以我们要求的就变成了 $[x^{W}]\frac{1}{(1-x)^{n+1}}\sum_{k=0}^{c_{1}+c_{2}....c_{n}}A_{k}g(x)^{k}$

我们考虑对每一个 $k$ ,算出 $[x^{W}]\frac{1}{(1-x)^{n+1}}g(x)^{k}$ ，即 $[x^{W-k}]\frac{1}{(1-x)^{n+k+1}}$ ，直接广义二项式定理展开，答案为 $\binom{W+n}{W-k}$ 即 $\binom{W+n}{n+k}$

补充：如何计算第二类斯特林数行?

$n\brace m$ = $\sum_{i=0}^{m}\binom{m}{i}(-1)^{i}(m-i)^{n}$

#include<bits/stdc++.h>
#define ll long long
#define mk(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define cs const
using namespace std;
cs int g=3;
const int N=8e5+10;
const int mod=998244353;
typedef vector<int> poly;
int rev[N],inv[N],fac[N],invf[N];
int n,m,len,d,x,k;
poly a;
int mul(int x,int y){return (ll)x*y%mod;}
int add(int x,int y){return x+y>=mod?x+y-mod:x+y;}
int dec(int x,int y){return x-y>=0?x-y:x-y+mod;}
int ksm(int x,int y){ll ans=1;for (;y;y>>=1,x=mul(x,x)) if (y&1) ans=mul(ans,x);return ans;
}
int read(){int f=1,x=0; char c=getchar();while (c<'0'||c>'9'){if (c=='-')f=-1;c=getchar();}while (c>='0'&&c<='9'){x=add(mul(x,10),c-'0');c=getchar();}return x; 
}
int init(int x){int len=1,d=0;while (len<x) {len<<=1;d++;}for (int i=0;i<len;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(d-1));return len;
}
int BSGS(int X,int Y){int now=floor(sqrt(mod));int s=ksm(X,now);map<int,int>mp;int t=1;int sum=Y;for (int i=0;i<now;i++){mp[sum]=i; sum=mul(sum,X);}int s1=1;for (int i=0;i<mod;i+=now){s1=mul(s1,s);if (mp[s1]) return i+now-mp[s1];}return 0;
}
void prep(){inv[0]=inv[1]=1;for (int i=2;i<N;i++) inv[i]=mul(inv[mod%i],(mod-mod/i));invf[0]=1;for (int i=1;i<N;i++) invf[i]=mul(invf[i-1],inv[i]);fac[0]=1;for (int i=1;i<N;i++) fac[i]=mul(fac[i-1],i);
}
int lalala(int x){int now=BSGS(g,x);return ksm(g,now/2);
}
void out(poly a){for (int i=0;i<a.size();i++) printf("%d ",a[i]);puts("\n");
}
inline poly NTT(poly a,int t) {for (int i=0;i<a.size();i++) if (i<rev[i]) swap(a[i],a[rev[i]]);for (int i=1;i<a.size();i<<=1) {int s=(i<<1);int wn=ksm(g,(mod-1)/s);if (t==-1) wn=ksm(wn,mod-2);for (int j=0;j<a.size();j+=s) {int w=1;for (int k=j;k<j+i;k++) {int x=a[k],y=mul(a[k+i],w);a[k]=add(x,y); a[k+i]=dec(x,y);w=mul(w,wn);}}}if (t==-1){ll w=ksm(a.size(),mod-2);for (int i=0;i<a.size();i++) a[i]=mul(a[i],w);}return a;
}
inline poly get_down(poly a){for (int i=0;i<a.size()-1;i++) a[i]=mul(a[i+1],i+1);a.pop_back();return a;
}
inline poly get_up(poly a){a.push_back(0);for (int i=a.size()-1;i>0;i--) a[i]=mul(a[i-1],inv[i]);a[0]=0;return a; 
}
inline poly operator +(poly a,poly b){a.resize(max(a.size(),b.size()));b.resize(max(a.size(),b.size()));for (int i=0;i<a.size();i++) a[i]=add(a[i],b[i]);return a; 
}
inline poly operator -(poly a,poly b){a.resize(max(a.size(),b.size()));b.resize(max(a.size(),b.size()));for (int i=0;i<a.size();i++) a[i]=dec(a[i],b[i]);return a;
}
inline poly operator *(poly a,int x){x=(mod+x)%mod;for (int i=0;i<a.size();i++) a[i]=mul(a[i],x);return a;
}
inline poly shift(poly a,int x,int m){int n=(int)a.size();n-=x;if (n<=0) return poly(1,0);poly b(min(n,m),0);for (int i=max(0,-x);i<min(n,m);i++) b[i]=a[i+x];return b;
}
inline poly operator *(poly a,poly b){int n=a.size(),m=b.size(); int len=init(n+m-1);a.resize(len);b.resize(len);a=NTT(a,1); b=NTT(b,1);for (int i=0;i<a.size();i++) a[i]=mul(a[i],b[i]);a=NTT(a,-1);a.resize(n+m-1);return a;
}
inline poly get_inv(poly a){poly b,d;b.pb(ksm(a[0],mod-2)); d.pb(a[0]);int now=1;while (now<a.size()) {now<<=1; poly c=b;c=c*c;for (int i=(now>>1);i<now&&i<a.size();i++) d.pb(a[i]);c=c*d;c.resize(now); b=b*2;  b=b-c;}b.resize(a.size());return b;
}
inline poly ln(poly a){poly c=get_up(get_inv(a)*get_down(a));c.resize(a.size());return c;}
inline poly exp(poly a){poly b,d;b.pb(1); d.pb(a[0]);int now=1;while (now<a.size()){now<<=1;for (int i=(now>>1);i<now&&i<a.size();i++) d.pb(a[i]);poly c=b;c.resize(now);c=ln(c)-d;for (int i=0;i<c.size();i++) c[i]=(mod-c[i])%mod;c[0]=add(c[0],1); b=b*c; b.resize(now); }	b.resize(a.size());return b;
}
inline poly ksm(poly a,int k){int n=(int)a.size();int i=0;while (i<n&&!a[i]) i++;int v=a[i];a=a*ksm(v,mod-2);a=shift(a,i,n);a=exp(ln(a)*k);a=shift(a,-i*k,n);a=a*v;return a;
}
inline poly Sqrt(poly a){poly b,d;b.pb(lalala(a[0])); d.pb(a[0]);b[0]=min(b[0],mod-b[0]);int now=1;while (now<a.size()){now<<=1; poly c=b;for (int i=(now>>1);i<now&&i<a.size();i++) d.pb(a[i]);c.resize(now);c=get_inv(c);c=c*d;c.resize(now);b=b+c;for (int i=0;i<now;i++) b[i]=mul(b[i],inv[2]);}b.resize(a.size());return b;
}
long long W;
int c[N];
poly f[N];
poly Stirling2_row(int n){poly f(n+1,0),g(n+1,0);for (int i=0;i<=n;i++) if (i&1) f[i]=dec(0,invf[i]); else f[i]=invf[i];for (int i=0;i<=n;i++) g[i]=mul(ksm(i,n),invf[i]);f=f*g;f.resize(n+1);return f;
}
poly solve(int l,int r){if (l==r) return f[l];else{int mid=(l+r)/2;return solve(l,mid)*solve(mid+1,r);}
}
int main(){scanf("%d%lld",&n,&W);W%=mod;prep();for (int i=1;i<=n;i++) scanf("%d",&c[i]);for (int i=1;i<=n;i++){f[i]=Stirling2_row(c[i]);for (int j=0;j<f[i].size();j++) f[i][j]=mul(f[i][j],fac[j]);}poly ans=solve(1,n);int s=1;for (int i=1;i<=n;i++) s=1ll*((W+i)%mod)*s%mod*inv[i]%mod;int s_fin=0;for (int i=0;i<ans.size();i++){s_fin=add(s_fin,mul(s,ans[i]));s=mul(s,inv[n+i+1]);s=1ll*s*((W-i+mod)%mod)%mod;}printf("%d\n",s_fin);
}