专栏文章

abc425E || Count Sequences 2

kkanlla
AT_abc425_e题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@minrqj03
此快照首次捕获于
2025/12/02 07:16
3 个月前
此快照最后确认于
2025/12/02 07:16
3 个月前
查看原文
赛时脑子没转弯所以写了一个很唐的做法，挂上来图一乐。

思路

不考虑模数的话，是一道很典的组合数学。我们先假设每个数都不同，令 sum=∑i=1nAisum=\sum\limits_{i=1}^{n} A_i，那么其贡献应该是 sum!sum!。但因为会有同样的数出现多次，所以我们考虑去重。注意到我们只用每个数之间没有很大关系，因此我们只需要将每个数多算的排列去掉即可，即对于 AiA_i 来说，再除掉 Ai!A_i!。因此答案就是 sum!∏i=1nAi!\dfrac{sum!}{\prod\limits_{i=1}^n A_i!}。
但模数不保证是质数，我们不能直接求逆元，所以我们应该用什么方式来避免掉除这一操作。发现 AiA_i 应该很小，所以我们可以直接预处理出每个数的所有质因数。这个时候除的本质就是将答案有的质因数减掉一部分，于是我们就把除法变成了减法！
不过这个思路就图一乐吧，因为确实不优而且复杂度挺危险，建议学习其它题解的做法。

代码

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

评论

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

正在加载评论...