题解：AT_abc425_e [ABC425E] Count Sequences 2

· · 题解

题目即求可重集排列方案数，我们知道答案为

{\sum c_i \choose c_1, c_2, \dots c_n} = \frac{(\sum c_i)!}{\prod c_i!}

证明是考虑其中分子为不考虑重复数的排列数，分母为相同数字的排列数。

但是我们知道模意义下除法需要逆元，而 a 在模 p 意义下有逆元当且仅当 \gcd(a, p) = 1，但是题目的 p 是现场给定的，显然不能保证该性质。注意到 \sum c_i \leq 5000 非常小，我们考虑对每个数进行质因数分解，计算每个质数在答案中的指数即可，这样除法就转化为了指数的减法。我们预处理每个数的质因数分解，计算阶乘时暴力枚举每个质因数，时间复杂度为 \mathcal{O}(\sum c\sqrt{\sum c} + (\sum n)\omega(c))，其中 \omega(c) 是不超过 c 的数的最大质因数数量，显然非常小，于是可以通过。

Code：

#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;
}