【题意】给出K(<=1000)种颜色的球,球的总数不超过1000个,第i种颜色的球的最后一个位置需要在第i+1种颜色最后一个球前面,问这样有多少种排列方式。
【分析】一看就发现是组合数学,可是我数学已经忘光了,而且还没开始做数学专题,导致直接不会写了,然后想着换种方法用DP求,然后就没时间了,唉;其实就是从后往前推,最后一种颜色的最后一个球先固定放在现在能放的最后面,然后对于每一种颜色的求分别求C(还剩下的位置数量,这种颜色的总数-1),最后把这些都乘起来就可以了,中间C()的除法用乘法逆元即可。由于球的总数不超过1000,所以阶乘不需要预处理也可以(说来惭愧,这是我第一次用乘法逆元,所以这场掉分是必须的)。
【AC CODE】31ms
#include <cstdio> #include <cstring> #include <cctype> #include <cmath> #include <set> //#include <unordered_set> #include <queue> #include <stack> #include <vector> #include <string> #include <algorithm> using namespace std; typedef long long LL; #define rep(i,a,n) for(int i = a; i < n; i++) #define repe(i,a,n) for(int i = a; i <= n; i++) #define per(i,n,a) for(int i = n; i >= a; i--) #define clc(a,b) memset(a,b,sizeof(a)) const int INF = 0x3f3f3f3f, MAXN = 1000+10; const LL MOD = 1000000007; LL fact(int n) { LL ans = 1; repe(i,2,n) ans = (ans*i)%MOD; return ans; } LL pow_mod(LL x, int n) { LL ans = 1; while(n) { if(n&1) ans = (ans*x)%MOD; x = (x*x)%MOD; n >>= 1; } return ans; } LL dv(LL a, LL b) { return a*pow_mod(b,MOD-2)%MOD; } LL cal(int n, int m) { LL fn = fact(n),tmp = fact(m)*fact(n-m)%MOD; return dv(fn,tmp); } int main() { #ifdef SHY freopen("d:\\1.txt", "r", stdin); #endif int n; scanf("%d", &n); LL ans = 1,sum = 0; rep(i,0,n) { LL a; scanf("%I64d", &a); sum += a; ans = ans*cal(sum-1,a-1)%MOD; } printf("%I64d\n", ans); return 0; }