abc425E || Count Sequences 2

kanlla · 2025-09-28 11:13:18 · 题解

赛时脑子没转弯所以写了一个很唐的做法，挂上来图一乐。

思路

不考虑模数的话，是一道很典的组合数学。我们先假设每个数都不同，令 sum=\sum\limits_{i=1}^{n} A_i，那么其贡献应该是 sum!。但因为会有同样的数出现多次，所以我们考虑去重。注意到我们只用每个数之间没有很大关系，因此我们只需要将每个数多算的排列去掉即可，即对于 A_i 来说，再除掉 A_i!。因此答案就是 \dfrac{sum!}{\prod\limits_{i=1}^n A_i!}。

但模数不保证是质数，我们不能直接求逆元，所以我们应该用什么方式来避免掉除这一操作。发现 A_i 应该很小，所以我们可以直接预处理出每个数的所有质因数。这个时候除的本质就是将答案有的质因数减掉一部分，于是我们就把除法变成了减法！

不过这个思路就图一乐吧，因为确实不优而且复杂度挺危险，建议学习其它题解的做法。

代码

#include<queue>
#include<vector>
#include<iostream>
#define int long long
using namespace std;
const int N=5005;
int t,n,ans,mod,sum,Max,qzh[N],A[N],cnt[N];
vector<pair<int,int> > num[N];
int qmi(int x,int y,int an=1){
    while(y){
        if(y&1) an=an*x%mod;
        x=x*x%mod,y>>=1;
    }
    return an;
}
void solve(){
    cin>>n;sum=Max=0,ans=1;
    for(int i=1;i<=n;i++){
        cin>>A[i];sum+=A[i];Max=max(Max,A[i]);
        qzh[A[i]]++;
    }
    int s=0;
    for(int i=Max;i>=1;i--){
        s+=qzh[i];
        for(auto a:num[i]) cnt[a.first]-=s*a.second;
    }
    for(int i=1;i<=sum;i++)
        for(auto a:num[i]) cnt[a.first]+=a.second;
    for(int i=1;i<=sum;i++){
        if(cnt[i]) ans=ans*qmi(i,cnt[i])%mod;
        cnt[i]=qzh[i]=0;
    }
    cout<<ans<<"\n";
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>t>>mod;
    for(int i=2;i<=5000;i++){
        int x=i;
        for(int j=2;j*j<=x;j++){
            int c=0;
            while(x%j==0){c++;x/=j;}
            if(c) num[i].push_back({j,c});
        }
        if(x!=1) num[i].push_back({x,1});
    }
    while(t--) solve();
    return 0;
}