专栏文章

题解：P2429 制杖题

PPJM2008
P2429题解参与者 2已保存评论 2

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@minz37oz
此快照首次捕获于
2025/12/02 10:42
3 个月前
此快照最后确认于
2025/12/02 10:42
3 个月前
查看原文
这题其实不太制杖吧

主要思路

首先 m≤109m\le10^9，暴力枚举大概率会超时。注意到 nn 数据范围较小，n≤20n\le20，很自然地想到暴力地用容斥原理筛，即 ∑I⊆[n],I≠∅(−1)∣I∣−1⌊m∏i∈Ipi⌋\sum_{I\subseteq[n],I\ne\emptyset}(-1)^{|I|-1}\lfloor\frac{m}{\prod_{i\in I}p_i}\rfloor 状压枚举 [n][n] 的每个非空子集求和即可。复杂度 O(2nn)O(2^nn)。
CPP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=376544743;
ll n,m,p[39],pro,ans,f;
int main(){
	cin>>n>>m; for(int i=1;i<=n;i++) cin>>p[i];
	for(int i=1;i<(1<<n);i++){
		f=-1; pro=1;
		for(int j=1;j<=n;j++){
			if(i&(1<<(j-1))){
				f*=-1; pro*=p[j]; if(pro>m) break;
			}
		}
		ans+=f*(m/pro*(m/pro+1)/2%mod*pro%mod)%mod; ans%=mod;
	}
	cout<<ans<<endl;
	return 0;
}
提交发现 TLE #1,2,3，疑似是因为 #1,2,3 n>20n>20（
考虑优化。注意到 ∣I∣|I| 较大时 ∏i∈Ipi\prod_{i\in I}p_i 很大（具体地，有 ∣I∣≥10|I|\ge10 时 ∏i∈Ipi>109>m\prod_{i\in I}p_i>10^9>m），故可将状压枚举改为 DFS 枚举，若当前枚举的质数乘积已经超过 mm 则剪枝，即可通过此题。

AC代码

CPP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=376544743;
ll n,m,p[39],ans;
void dfs(ll num,ll f,ll pro){
	if(num==n+1){
		if(pro==1) return;
		ans+=f*(m/pro*(m/pro+1)/2%mod*pro%mod)%mod; ans%=mod; return;
	}
	dfs(num+1,f,pro);
	if(pro*p[num]<=m) dfs(num+1,-f,pro*p[num]);
}
int main(){
	cin>>n>>m; for(int i=1;i<=n;i++) cin>>p[i];
	dfs(1,-1,1); cout<<ans<<endl;
	return 0;
}

评论

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

正在加载评论...