小a是一名强迫症患者，现在他要给一群带颜色的珠子排成一列，现在有N中颜色，其中第i中的颜色的珠子有s[i]个，要求排列中第i种颜色的最后一个珠子一定要排在第i+1种颜色的最后一个珠子前面，问有多少种方案 ΣS<=50W
组合数学法，一种一种颜色来排，我们发现对于一种颜色i，相当于在前面所有的空位种选出s[i]-1个，这个可以用组合数计算，其值为C(-1+Σs[i],s[i]-1)，组合数我们可以用阶乘+逆元搞定
#include#include #include #define LL long long#define N 500000 #define M 998244353using namespace std;LL js[N+10],inv[N+10],A=1; int n,x,c=0;inline LL C(int n,int m){ return js[n]*inv[m]%M*inv[n-m]%M;}inline LL pow(LL x,LL k,LL& s){ for(s=1;k;x=x*x%M,k>>=1) if(k&1) s=s*x%M;}int main(){ for(int i=*js=*inv=1;i<=N;++i) js[i]=js[i-1]*i%M; pow(js[N],M-2,inv[N]); for(int i=N;i;--i) inv[i-1]=inv[i]*i%M; for(scanf("%d%d",&n,&c);--n;){ scanf("%d",&x); c+=x-1; A=A*C(c,x-1)%M; ++c; } printf("%lld\n",A);}