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 ;

 }

巴特西

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

最新文章

热门文章