题解：P2429 制杖题

· · 题解

这题其实不太制杖吧

主要思路

首先 m\le10^9，暴力枚举大概率会超时。注意到 n 数据范围较小，n\le20，很自然地想到暴力地用容斥原理筛，即

\sum_{I\subseteq[n],I\ne\emptyset}(-1)^{|I|-1}\lfloor\frac{m}{\prod_{i\in I}p_i}\rfloor

状压枚举 [n] 的每个非空子集求和即可。复杂度 O(2^nn)。

#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>20（

考虑优化。注意到 |I| 较大时 \prod_{i\in I}p_i 很大（具体地，有 |I|\ge10 时 \prod_{i\in I}p_i>10^9>m），故可将状压枚举改为 DFS 枚举，若当前枚举的质数乘积已经超过 m 则剪枝，即可通过此题。

AC代码

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