2019.5.25 提高A组 T1 JZOJ 4786 小a的强迫症

$Description$

有$n$种颜色的珠子每个珠子各有$a_i$个，现在要用它们组成排列，但要求在排完第$i$种颜色之前不能先排完第$i+1$个颜色，求排列的方案数

$n\le 10^5,\sum a\le 5\times 10^5$

---

$Solution$

首先我们很容易打出暴力的代码，然后就有40分了

#include<cstdio> #include<cctype> using namespace std;int n,ans,a[100001],sum; inline long long read() { char c;int d=1;long long f=0; while(c=getchar(),!isdigit(c))if(c==45)d=-1;f=(f<<3)+(f<<1)+c-48; while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48; return d*f; } inline void dfs(int dep,int *a) { for(register int i=n;i>=0;i--) if(a[i]==0&&a[i-1]>0) return; if(dep>sum) {ans++;return;} for(register int i=1;i<=n;i++) if(a[i]) { a[i]--; dfs(dep+1,a); a[i]++; } } signed main() { n=read(); for(register int i=1;i<=n;i++) a[i]=read(),sum+=a[i]; dfs(1,a); printf("%d\n",ans); }

然后我们分析发现每次就是在剩余的空位种选择$a_i$-1个，这样我们一个倒序循环+组合数计数就完事了

直接费马算逆元时间复杂度：$O(sumlogsum+n)$，$O(sum)$推复杂度$O(sum+n)$（速度榜rk1）

---

$Code$

#include<cstdio> #include<cctype> #define mod 998244353 using namespace std;int n,a[100001],sum; long long fac[500001],inv[500001],ans=1; inline long long ksm(long long x,long long y) { long long ans=1; for(;y;y>>=1,(x*=x)%=mod) if(y&1) (ans*=x)%=mod; return ans; } inline long long read() { char c;int d=1;long long f=0; while(c=getchar(),!isdigit(c))if(c==45)d=-1;f=(f<<3)+(f<<1)+c-48; while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48; return d*f; } inline long long C(int n,int m){return fac[n]*inv[n-m]%mod*inv[m]%mod;} signed main() { n=read(); for(register int i=1;i<=n;i++) a[i]=read(),sum+=a[i]; fac[0]=inv[0]=1; for(register int i=1;i<=sum;i++) fac[i]=fac[i-1]*i%mod; inv[sum]=ksm(fac[sum],mod-2); for(register int i=sum-1;i>0;i--) inv[i]=inv[i+1]*(i+1)%mod;//O(sum)推逆元 for(register int i=n;i>0;i--) { (ans*=C(sum-1,a[i]-1))%=mod;//在剩下的空中选a[i]-1个 sum-=a[i];//空位减少 } printf("%lld",ans); }