Codeforces554C:Kyoya and Colored Balls(组合数学计算+费马小定理)

题意:
有k种颜色,每种颜色对应a[i]个球,球的总数不超过1000
要求第i种颜色的最后一个球,其后面接着的必须是第i+1种颜色的球
问一共有多少种排法
Sample test(s)
input

output

input

output

Note

In the first sample, we have 2 balls of color 1, 2 balls of color 2, and 1 ball of color 3. The three ways for Kyoya are:


思路:
首先我们容易想到我们必须要确定每种颜色最后一个球的放法
所有对于最后一种颜色,假设这种颜色有b个球,而总球数为a
那么必然有一个球是放在最后一个位置的,那么剩下的球就是z=C(b-1,a-1)种方法
那么对于倒数第二种球,假设有x个,此时总球数位y=a-b
那么之前已经有z种方法了,而对于每一种放法,此时倒数第二种颜色拿出一个作为最后一个球的话,它对于每种放法必然只有一个固定方法,位置是最后一个没有放球的位置,这样既保证放法符合要求,而剩下的球就有C(x-1,y-1)种放法
然后相乘得到最后一种颜色与最后第二种颜色的方法,以此类推。。
可以使用费马小定理来优化组合数计算

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<cmath>
using namespace std;
#define MOD 1000000007
#define ll long long
ll n;
ll a[];
ll fac[];
ll pow_mod(ll a,ll i)
{
if(i==)
return %MOD;
ll t=pow_mod(a,i/);
ll ans=t*t%MOD;
if(i%==)
ans=ans*a%MOD;
return ans;
}
ll work(ll m,ll i)
{
return ( (fac[m]%MOD)* ( pow_mod(fac[i]*fac[m-i]%MOD ,MOD-)%MOD))%MOD;
} int main()
{
fac[]=;
for(int i=;i<;i++)
fac[i]=(fac[i-]*i)%MOD;
ll ans=;
ll sum=;
scanf("%I64d",&n);
for(int i=;i<=n;i++)
{
scanf("%I64d",&a[i]);
sum+=a[i];
}
for(int i=n;i>=;i--)
{
ans=ans*work(sum-,a[i]-)%MOD;
sum-=a[i];
}
printf("%I64d\n",ans);
return ;
}
 
上一篇:java spark淘宝大数据分析可视化系统(源码+数据+报告)


下一篇:结合《剑指offer(第二版)》面试题51来谈谈归并排序