[JZOJ4786]小a的强迫症

题目大意：

有\(n(n\le10^5)\)种颜色的珠子，第\(i\)种颜色有\(num[i]\)个。你要把这些珠子排成一排，使得第\(i\)种颜色的最后一个珠子一定在第\(i+1\)种珠子的最后一个珠子之前，求方案数。

思路：

\(f_i\)表示排完前\(i\)种颜色的方案数，显然前\(num[i]-1\)个可以瞎放，剩下一个一定要放最后，所以\(f_i=f_{i-1}\times\frac{(\sum_{j\le i}num[j]-1)!}{(\sum_{k<i}num[k])!(num[i]-1)!}\)。

时间复杂度\(\mathcal O(n+\sum num[i])\)。

源代码：

#include
    
     #include
     
      inline int getint() {    register char ch;    while(!isdigit(ch=getchar()));    register int x=ch^'0';    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');    return x;}typedef long long int64;const int N=1e5+1,S=5e5+1,mod=998244353;int num[N],fac[S],ifac[S];void exgcd(const int &a,const int &b,int &x,int &y) {    if(!b) {        x=1,y=0;        return;    }    exgcd(b,a%b,y,x);    y-=a/b*x;}inline int inv(const int &x) {    int ret,tmp;    exgcd(x,mod,ret,tmp);    return (ret%mod+mod)%mod;}inline int calc(const int &s,const int &k) {    return (int64)fac[s+k-1]*ifac[s]%mod*ifac[k-1]%mod;}int main() {    const int n=getint();    int sum=0;    for(register int i=1;i<=n;i++) {        num[i]=getint();        sum+=num[i];    }    for(register int i=fac[0]=1;i<=sum;i++) {        fac[i]=(int64)fac[i-1]*i%mod;    }    ifac[sum]=inv(fac[sum]);    for(register int i=sum;i>=1;i--) {        ifac[i-1]=(int64)ifac[i]*i%mod;    }    sum=0;    int ans=1;    for(register int i=1;i<=n;i++) {        ans=(int64)ans*calc(sum,num[i])%mod;        sum+=num[i];    }    printf("%d\n",ans);    return 0;}