专栏文章

题解：AT_abc425_e [ABC425E] Count Sequences 2

CClaire0918
AT_abc425_e题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@minr9ntv
此快照首次捕获于
2025/12/02 07:03
3 个月前
此快照最后确认于
2025/12/02 07:03
3 个月前
查看原文
题目即求可重集排列方案数，我们知道答案为
(∑cic1,c2,…cn)=(∑ci)!∏ci!{\sum c_i \choose c_1, c_2, \dots c_n} = \frac{(\sum c_i)!}{\prod c_i!}
证明是考虑其中分子为不考虑重复数的排列数，分母为相同数字的排列数。
但是我们知道模意义下除法需要逆元，而 aa 在模 pp 意义下有逆元当且仅当 gcd⁡(a,p)=1\gcd(a, p) = 1，但是题目的 pp 是现场给定的，显然不能保证该性质。注意到 ∑ci≤5000\sum c_i \leq 5000 非常小，我们考虑对每个数进行质因数分解，计算每个质数在答案中的指数即可，这样除法就转化为了指数的减法。我们预处理每个数的质因数分解，计算阶乘时暴力枚举每个质因数，时间复杂度为 O(∑c∑c+(∑n)ω(c))\mathcal{O}(\sum c\sqrt{\sum c} + (\sum n)\omega(c))，其中 ω(c)\omega(c) 是不超过 cc 的数的最大质因数数量，显然非常小，于是可以通过。
Code：
CPP
#include<bits/stdc++.h>
#define mem(a, v) memset(a, v, sizeof(a))

using namespace std;

const int maxn = 3e5 + 10, maxa = 5000;

int t, n, mod;
long long res;
int a[maxn], cnt[maxa + 10];
vector<pair<int, int> > d[maxa + 10];

int main(){
    scanf("%d %d", &t, &mod);
    for (int i = 2; i <= maxa; i++){
        int now = i;
        for (int j = 2; j * j <= i; j++){
            if (!(now % j)){
                int cnt = 0;
                for (;!(now % j); now /= j, cnt++);
                d[i].push_back(make_pair(j, cnt));
            }
        }
        now > 1 && (d[i].push_back(make_pair(now, 1)), 1538);
    }
    while (t--){
        scanf("%d", &n), a[n + 1] = 0, res = 1;
        for (int i = 1; i <= n; i++){
            scanf("%d", &a[i]), a[n + 1] += a[i];
        }
        for (int i = 2; i <= a[n + 1]; i++){
            for (auto x: d[i]){
                cnt[x.first] += x.second;
            }
        }
        for (int i = 1; i <= n; i++){
            for (int j = 2; j <= a[i]; j++){
                for (auto x: d[j]){
                    cnt[x.first] -= x.second;
                }
            }
        }
        for (int i = 2; i <= maxa; i++){
            for (;cnt[i]; res = res * i % mod, cnt[i]--);
        }
        printf("%lld\n", res);
    }

return 0;
}

评论

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

正在加载评论...