题解：SP28304 ADATEAMS - Ada and Teams

首先，我们分析一下题意是什么。从

N

所学校选出

A

所，有

C_N^A

种选法。每所学校从

B

名学生选出

D

名有

C_B^D

种选法，选出了

A

所学校，所以题目就是让我们求

C_N^A \times {(C_B^D)}^A

。

现在的问题就是如何算这个式子。我们知道：

C_n^m=\frac{n\times (n-1) \times ... \times n-m+1}{1\times 2\times ... \times m}

即：

C_n^m=\frac{\frac{n!}{(n-m)!}}{m!}

所以我们可以提前处理出前缀和。但是，这里涉及除法，又要取模。所以我们要求逆元。不会的可以参考这道题的题解。

对于

{(C_B^D)}^A

，写一个快速幂即可。

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
ll n,a,b,d,fac[1000001];
int qpow(int a,int b){
    int t=1;
    ll c=a,r=1;
    while(t<=b){
        if(t&b){
            r*=c;
            r%=mod;
        }
        c*=c;
        c%=mod;
        t<<=1;
    }
    return r;
}
int inv(int p){
    return qpow(p,mod-2);
}
ll c(ll x,ll y){
    return 1ll*fac[x]*inv(fac[x-y])%mod*inv(fac[y])%mod;
}
int main(){
    fac[0]=1;
    for(int i=1;i<=1e6;i++){
        fac[i]=fac[i-1]*i%mod;
    }
    while(~scanf("%lld%lld%lld%lld",&n,&a,&b,&d)){
        printf("%lld\n",qpow(c(b,d),a)*c(n,a)%mod);
    }
    return 0;
}

好了，最后祝大家做题愉快，满屏 AC！

题解：SP28304 ADATEAMS - Ada and Teams

文章操作

相关推荐

评论

题解：SP28304 ADATEAMS - Ada and Teams