ARC134C The Majority
小清新数学题。（反正我做不出来）
简要题意
有\(K\)个箱子，编号为\(1\)到\(K\)的箱子。起初，所有箱子都是空的。
史努克有一些球，球上写着\(1\)到\(N\)的整数。在这些球中，有\(a_i\)个球上写着数字\(i\)。带有相同数字的球无法区分。
史努克决定把他所有的球都放进箱子里。他希望每个箱子里写着数字\(1\)的球都是多数。换句话说，每个箱子里，写着数字\(1\)的球的数量应该多于其他球的数量,即占到一半以上。
找出这样放置球的方法数，结果对\(998244353\)取模。
当存在一对整数\((i,j)\)满足\(1≤i≤K,1≤j≤N\)，并且在第\(i\)个箱子中，写着数字\(j\)的球的数量不同时，两种方式被认为是不同的。
思路
把每个 1 号球先和每个不是 1 号球配对一下，再在每个盒子里都放 1 个 1 号球。
这样子剩下了 \(a_1-\sum\limits_{i=2}^na_i-k\) 个 1 号球。
同时保证了 1 号球是多数的条件。
现在使 \(a_1-\sum\limits_{i=2}^na_i-k \to a_1\)。
接下来球都可以任意放，对于单个种类的球看做有 \(a_i\) 个球，放到 \(k\) 个盒子里，允许空放的问题。
这个经典问题的答案是 \(C_{a_i+k-1}^{k-1}\)。
最终答案是
\[\prod_{i=1}^n C_{a_i+k-1}^{k-1}
\]
CODE
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 998244353
const int maxn=1e5+5;
ll n,k,sum,ans;
ll a[maxn],fac[maxn],inv[maxn];
ll ksm(ll x,ll y)
{
ll sum=1;
for(;y;y/=2,x=x*x%mod) if(y&1) sum=sum*x%mod;
return sum;
}
ll C(ll n,ll m)
{
if(n<=m) return 1;
ll sum=inv[m];
for(ll i=n-m+1;i<=n;i++) sum=sum*i%mod;
return sum;
}
int main()
{
scanf("%lld%lld",&n,&k);
fac[0]=1;
for(int i=1;i<=k;i++) fac[i]=fac[i-1]*i%mod;
inv[k]=ksm(fac[k],mod-2);
for(int i=k-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
for(int i=2;i<=n;i++) sum+=a[i];
a[1]=a[1]-sum-k;
if(a[1]<0)
{
printf("0");
return 0;
}
ans=1;
for(int i=1;i<=n;i++)
ans=ans*C(a[i]+k-1,k-1)%mod;
printf("%lld",ans);
}