【NOIP2016提高A组模拟9.17】小a的强迫症

本文主要是介绍【NOIP2016提高A组模拟9.17】小a的强迫症，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

Input

第一行n
第二行n个数，代表每种颜色的数量

Output

答案

Sample Input

3
2 2 1

Sample Output

3

Data Constraint

$n<=100000$

Solution

假设当前做到第i种颜色，数量为a，第1到第i-1种颜色的数量和为s
那么当前已经有s个球了，为了保证合法，必须把第i中颜色的球放一个在最后面，还是a-1个球插到前面s个球中间和两边去
想到了什么？隔板问题！
简单来说，答案就是$C_{s+a-1}^{a-1}$乘起来就行了

Code

#include<cstdio>
#include<algorithm>
#include<cmath>
#define ll long long
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define mo 998244353
using namespace std;
ll jc[1010000];
ll mi(ll a,ll b)
{if(b==0) return 1ll;if(b==1) return a;ll c=mi(a,b/2);if(b%2==0) return (c*c)%mo;else return (((c*c)%mo)*a)%mo;
}
ll C(ll m,ll n)
{return ((((jc[m]*mi(jc[n],mo-2))%mo)*mi(jc[m-n],mo-2))%mo)%mo;
}
int main()
{int n;scanf("%d",&n);jc[0]=1;fo(i,1,1000000) jc[i]=((ll)i*jc[i-1])%mo;ll ans=1,s=0;fo(i,1,n){ll x;scanf("%lld",&x);ans=(ans*C(x+s-1,x-1))%mo;s+=x;}printf("%lld",ans);
}

这篇关于【NOIP2016提高A组模拟9.17】小a的强迫症的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---