题解：SP28304 ADATEAMS - Ada and Teams

· · 题解

这是一个排列组合问题。

事先声明

如果你不懂排列是什么，请左转这个链接。\ 如果你不懂组合是什么，请左转这个链接。\ 如果你不懂乘法逆元是什么，请左转这个链接。

思路

由题面可知，我们需要求出 C^A_N \times (C^D_B)^A。\ 为什么呢？因为我们要从 N 所学校中选择 A 所学校参赛，所以前面是 C^A_N。（注意：这不是 A^A_N，因为这是组合，而非排列）

而且，我们还要在每一所学校的 B 名学生中选择 D 名参赛，所以每一所学校的选择方案数为 C^D_B。因为我们总共有 A 所学校参赛，所以后面是 (C^D_B)^A。

由思路到实现

我们试图直接实现的时候，会发现：N,A,B,D \le 10^6，想要实现低复杂度的求组合操作可以说是难如登天……吗？\ 经过 Deepseek の 提醒经过思考，我们能够想到一种很新的实现的方式：乘法逆元。

首先，我们处理 i（i \le 10^6，下同）对于 10^9 + 7 的乘法逆元，以及 i 的阶乘及其乘法逆元。\ 在以后对于计算 A 与 B 组合的处理中，我们可以直接返回 (((fact[A] \times invfact[B]) \bmod MOD) \times invfact[A - B]) \bmod MOD。其中， fact 代表阶乘数组，invfact 代表阶乘逆元数组。\ 最后，我们统计一下时间复杂度：初始化 O(10^6)，单次查询 O(1)，时间复杂度在可接受范围内。

代码

想抄代码的看过来：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 1000000007
int inv[1000005],fact[1000005],invfact[1000005];
int C(int n,int k)
{
    if(k < 0 || k > n) return 0;
    return 1LL * fact[n] * invfact[k] % MOD * invfact[n - k] % MOD;
}
int ksm(int n,int m)
{
    int ans = 1;
    while(m)
    {
        if(m & 1) ans = (ans * n) % MOD;
        n = (n * n) % MOD;
        m >>= 1;
    }
    return ans;
}
int work(int n,int a,int b,int d)
{
    return (C(n,a) * ksm(C(b,d),a)) % MOD;
}
signed main()
{
    inv[1] = 1;
    for(int i = 2;i <= 1000005;i++) inv[i] = (MOD - 1LL * (MOD / i) * inv[MOD % i] % MOD) % MOD;
    fact[0] = 1;
    for(int i = 1;i <= 1000000;i++) fact[i] = 1ll * fact[i - 1] * i % MOD;
    invfact[0] = 1;
    for(int i = 1;i <= 1000000;i++) invfact[i] = 1ll * invfact[i - 1] * inv[i] % MOD;
    int n,a,b,d;
    while(cin >> n >> a >> b >> d) cout << work(n,a,b,d) << endl;
    return 0;
}