专栏文章

题解：SP28304 ADATEAMS - Ada and Teams

RRyzen_9_9950X3D
SP28304题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioozxpy
此快照首次捕获于
2025/12/02 22:47
3 个月前
此快照最后确认于
2025/12/02 22:47
3 个月前
查看原文
这是一个排列组合问题。

事先声明

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

思路

由题面可知，我们需要求出 CNA×(CBD)AC^A_N \times (C^D_B)^A。
为什么呢？因为我们要从 NN 所学校中选择 AA 所学校参赛，所以前面是 CNAC^A_N。（注意：这不是 ANAA^A_N，因为这是组合，而非排列）
而且，我们还要在每一所学校的 BB 名学生中选择 DD 名参赛，所以每一所学校的选择方案数为 CBDC^D_B。因为我们总共有 AA 所学校参赛，所以后面是 (CBD)A(C^D_B)^A。

由思路到实现

我们试图直接实现的时候，会发现：N,A,B,D≤106N,A,B,D \le 10^6，想要实现低复杂度的求组合操作可以说是难如登天……吗？
经过 Deepseek の 提醒经过思考，我们能够想到一种很新的实现的方式：乘法逆元。
首先，我们处理 ii（i≤106i \le 10^6，下同）对于 109+710^9 + 7 的乘法逆元，以及 ii 的阶乘及其乘法逆元。
在以后对于计算 AA 与 BB 组合的处理中，我们可以直接返回 (((fact[A]×invfact[B]) mod MOD)×invfact[A−B]) mod MOD(((fact[A] \times invfact[B]) \bmod MOD) \times invfact[A - B]) \bmod MOD。其中， factfact 代表阶乘数组，invfactinvfact 代表阶乘逆元数组。
最后，我们统计一下时间复杂度：初始化 O(106)O(10^6)，单次查询 O(1)O(1)，时间复杂度在可接受范围内。

代码

想抄代码的看过来：
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...