题解：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，写一个快速幂即可。

#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！