[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<cstdio>
#include<cctype>
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;
}
