SP28304 题解

DecemberFox · 2024-02-07 19:31:37 · 题解

SP28304

题目分析

本题大致意思为从 n 所学校中选出 a 所后，然后再从这 a 所各有 b 人的学校中选出 d 名学生，求最终的方案数。

解法分析

本题需要排列组合及乘法逆元的前置知识。

本题为一个排列组合题目。

其中，从 n 所学校选 a 所学校共有 C^a_n 种方案，而从 1 所学校的 b 名学生中选出 d 名学生的方案数为 C^d_b，根据乘法原理在 a 所学校种就总共有 (C^d_b)^a 种方案，最后再乘上选取学校的方案数 C^a_n 即可。

即最终答案为 C^a_n\times (C^d_b)^a。

因为最终答案需要模 10^9+7，因此这里使用预处理阶乘及其乘法逆元的方法来计算组合数的值。

#include<iostream>
#include<cstdio>
namespace io
{
    void read()
    {
        return;
    }
    template<typename nowtype,typename ...nexttype>
    void read(nowtype &now,nexttype &...next)
    {
        register char c=getchar();
        register int n(1);
        now=0;
#define isdigit(c) ((c)>='0'&&(c)<='9')
        while(!isdigit(c)){if(c=='-') n=-1;c=getchar();}
        while(isdigit(c)){now=(now<<1)+(now<<3)+(c^48);c=getchar();}
#undef isdigit
        now*=n;
        read(next...);
    }
    template<typename nowtype>
    void write(nowtype num,char end='\n')
    {
        register unsigned long long unum(0);
        if(num<0) putchar('-'),unum=-num;
        else unum=num;
        register int c[35],top(0);
        do c[top++]=unum%10,unum/=10;while(unum);
        while(top) putchar(c[--top]+48);
        putchar(end);
    }
    template<typename nowtype,typename ...nexttype>
    void write(nowtype num,char end,nexttype ...next)
    {
        register unsigned long long unum(0);
        if(num<0) putchar('-'),unum=-num;
        else unum=num;
        register int c[35],top(0);
        do c[top++]=unum%10,unum/=10;while(unum);
        while(top) putchar(c[--top]+48);
        putchar(end);
        write(next...);
    }
}
//以上为快读快写
using namespace io;
namespace SOLVE
{
    typedef long long ll;
    typedef unsigned long long ull;
    typedef __int128 lll;
    typedef unsigned __int128 ulll;
    const int const1=1e6+10;
    const ll mod=1e9+7;
    ll f[const1],g[const1];
    ll pow(ll a,ll x)//快速幂
    {
        ll ans(1);
        while(x)
        {
            if(x&1) ans=ans*a%mod;
            a=a*a%mod;
            x>>=1;
        }
        return ans;
    }
    void init()//初始化阶乘及其逆元
    {
        ll i;
        f[0]=g[0]=1;
        for(i=1;i<const1;++i)
        {
            f[i]=f[i-1]*i%mod;
            g[i]=g[i-1]*pow(i,mod-2)%mod;
        }
    }
    ll C(ll n,ll m)//求组合数
    {
        return f[n]*g[m]%mod*g[n-m]%mod;
    }
    void solve()
    {
        ll n,a,b,d;
        init();
        while(scanf("%lld%lld%lld%lld",&n,&a,&b,&d)!=EOF) write(C(n,a)*pow(C(b,d),a)%mod);
    }
}
int main()
{
    SOLVE::solve();
    return 0;
}