题目
解题思路
当一种颜色
i
i
i被确定的时候，这种颜色可以放的方案为：
C
s
u
m
[
i
]
−
1
a
[
i
]
−
1
C_{sum[i]-1}^{a[i]-1}
Csum[i]−1a[i]−1 那么以此类推可得
∏
i
=
1
n
C
s
u
m
[
i
]
−
1
a
[
i
]
−
1
\prod_{i=1}^{n} C_{sum[i]-1}^{a[i]-1}
i=1∏nCsum[i]−1a[i]−1 有模数，用费马小定理处理一下即可。
代码
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
#define lw 998244353
using namespace std
;
ll n
,num
[100005],jc
[500005]={},s
,ans
=1;
ll
ksm(ll x
,ll y
){ll t
=1; for (;y
;y
>>=1,(x
*=x
)%=lw
) if (y
&1) (t
*=x
)%=lw
; return t
;}
ll
ni_yuan(ll x
){return ksm(x
,lw
-2)%lw
;}
ll
c(ll n
,ll m
){if (m
>n
) return 0; return (((jc
[n
]*ni_yuan(jc
[m
]))%lw
)*ni_yuan(jc
[n
-m
]))%lw
;}
int main(){
scanf("%lld",&n
); jc
[0]=1;
for (ll i
=1;i
<=n
;i
++) scanf("%lld",&num
[i
]),s
+=num
[i
];
for (ll i
=1;i
<=s
;i
++) jc
[i
]=(jc
[i
-1]*i
)%lw
;
for (ll i
=n
;i
>=1;i
--) ans
=(ans
*c(s
-1,num
[i
]-1))%lw
,s
-=num
[i
];
printf("%lld",ans
);
}
