【JZOJ 4786】 小a的強迫症

Description

Analysis

直接邊讀邊做，強制放一個在序列末端，其他的方案數模型就轉成n個盒子，m個球，放球，盒子可為空求方案數，用組合數解決即可。

Code

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=,mo=;
ll fac[N];
ll qmi(ll x,ll n)
{
    ll t=;
    for(;n;n>>=)
    {
        if(n&==) t=t*x%mo;
        x=x*x%mo;
    }
    return t;
}
ll ny(ll x)
{
    return qmi(x,mo-);
}
ll C(ll m,ll n)
{
    return fac[m]*ny(fac[n])%mo*ny(fac[m-n])%mo;
}
int main()
{
    fac[]=;
    for(int i=;i<=;i++) fac[i]=fac[i-]*i%mo;
    int n;
    ll x,s=,ans=;
    scanf("%d",&n);
    for(int i=;i<=n;i++)
    {
        scanf("%lld",&x);
        ans=ans*C(s+x-,x-)%mo;
        s+=x;
    }
    printf("%lld",ans);
    return ;
}