题目

题目描述

享国之日浅，国家无事。
B 君看到了 Z 君的第二题，觉得很难。于是自己出了一个简单题。大 A 是一名强迫症患者，现在他要给一群带颜色的珠子排成一列，现在有 n 种颜色，其中第 i 种颜色的珠子有 ai 个。要求排列中第 i 种颜色珠子的所有珠子，一定要排在第 i + 1 种颜色的第一个和最后一个珠子之间。问有多少种排列珠子的方案，因为方案数会很大，所以请输出答案对1000000007 取模之后的结果。

输入格式

第一行一个整数 n。以下 n 行，每行一个整数 ai。

输出格式

一行一个整数表示答案。

输入样例

输出样例

168

168

说明

对于 100% 的数据，满足 1 ≤ n ≤ 10^4 , 2 ≤ ai ≤ 15。对于 70% 的数据，满足 1 ≤ n ≤ 10^2。

题解

代码

#include<cstdio>
#include<iostream>
using namespace std;
#define MOD 1000000007
#define MAXN 100001
long long fact[MAXN],inv[MAXN];

long long pow(long long a,long long b){
    long long ans=1;
    while(b){
        if(b&1)ans=a*ans%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return ans%MOD;
}

long long c(long long m,long long n){
    return fact[m]*inv[n]%MOD*inv[m-n]%MOD;
}

void pre(){
    fact[0]=1;
    inv[0]=1;
    for(int i=1;i<MAXN;i++){
        fact[i]=fact[i-1]*i%MOD;
        inv[i]=pow(fact[i],MOD-2);
    }
}

int main(){
    long long x,y;
    pre();
    cin>>x;
    long long z=1;
    int s=0;
    for(int i=1;i<=x;i++){
        scanf("%lld",&y);
        z=z*c(s+y-2,y-2)%MOD;
        s+=y;
    }
    cout<<z;
    return 0;
}

#include<cstdio>

#include<iostream>

using namespace std;

#define MOD 1000000007

#define MAXN 100001

long long fact[MAXN],inv[MAXN];

long long pow(long long a,long long b){

long long ans=1;

while(b){

if(b&1)ans=a*ans%MOD;

a=a*a%MOD;

b>>=1;

}

return ans%MOD;

}

long long c(long long m,long long n){

return fact[m]*inv[n]%MOD*inv[m-n]%MOD;

}

void pre(){

fact[0]=1;

inv[0]=1;

for(int i=1;i<MAXN;i++){

fact[i]=fact[i-1]*i%MOD;

inv[i]=pow(fact[i],MOD-2);

}

int main(){

long long x,y;

pre();

cin>>x;

long long z=1;

int s=0;

for(int i=1;i<=x;i++){

scanf("%lld",&y);

z=z*c(s+y-2,y-2)%MOD;

s+=y;

}

cout<<z;

return 0;

}

发送评论编辑评论

题目