给定一个k表示颜色的种类从1到k
然后接下来k行， 每行一个数字， 代表该颜色的球有多少个
这些球都放在一个包中，然后依次拿出。 要求颜色i的最后一个球， 必须要排在颜色i+1的最后一个球前面， 1<=i<=k-1
我们先从小规模判断起来，
当k=2时，
当k=3时， a[2]-1个球可以在已经排好的 每个排列中的 a[0]+a[1] 个球中随便插， 因为已经排好（即位置不能变了），所以a[0]+a[1]个球可以看做是同一种颜色的球
那么这个随便插就相当于有多少种不同的排列。 可知是
这是在每个排列中随便插的结果， 总共有个排列， k=3时，总的取法是两个式子相乘
1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #include <algorithm> 5 #include <iostream> 6 #include <queue> 7 #include <stack> 8 #include <vector> 9 #include <map> 10 #include <set> 11 #include <string> 12 #include <math.h> 13 using namespace std; 14 #pragma warning(disable:4996) 15 typedef long long LL; 16 const int INF = 1<<30; 17 /* 18 19 */ 20 const int MOD = 1000000007; 21 int a[1000 + 10]; 22 LL fact[1000001]; 23 24 LL MyPow(LL a, LL b) 25 { 26 LL ret = 1; 27 while (b) 28 { 29 if (b & 1) 30 ret = ret * a % MOD; 31 a = a * a % MOD; 32 b >>= 1; 33 } 34 return ret; 35 } 36 LL C(int n, int m) 37 { 38 if (m > n || m < 0) return 0; 39 LL a = fact[n], b = fact[n - m] * fact[m] % MOD; 40 return a * MyPow(b, MOD - 2) % MOD;//除以一个数，等于乘以这个数的乘法逆元， 然后是在MOD的情况下 41 } 42 43 int main() 44 { 45 fact[0] = 1; 46 for (int i = 1; i < 1000001; ++i) 47 fact[i] = fact[i - 1] * i %MOD; 48 int n; 49 scanf("%d", &n); 50 for (int i = 0; i < n; ++i) 51 scanf("%d", &a[i]); 52 int sum = a[0]; 53 LL ans = 1; 54 for (int i = 1; i < n; ++i) 55 { 56 sum += a[i]; 57 ans = ans * C(sum - 1, sum - a[i] - 1) % MOD; 58 } 59 printf("%I64d ", ans); 60 return 0; 61 }
为什么在取模的情况下，除以一个数 会等于乘以这个数的逆元呢？
那么在%p的情况下 乘以xb， 那么就相当于乘以1， 然后就可以把分母给约掉。 而x叫做b模p的乘法逆元