【比賽記錄】2025CSP+NOIP 沖刺模擬賽合集Ⅳ
HZOJ NOIP2025模擬3
| A | B | C | D | Sum | Rank |
|---|---|---|---|---|---|
| 100 | 40 | 20 | 12 | 172 | 7/28 |
A. 變形怪
直接記憶化搜索即可。\(x\) 中包含前十個質數時答案最大，為 \(458123\)，可以接受。
Code
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
int m;
ll n,a[17];
__gnu_pbds::cc_hash_table<ll,__gnu_pbds::null_type> ans;
il void dfs(ll x){
// cout<<x<<'\n';
if(ans.find(x)!=ans.end()){
return ;
}
ans.insert(x);
if(!x){
return ;
}
for(int i=1;i<=m;i++){
dfs(x/a[i]);
}
}
int main(){
freopen("set.in","r",stdin);
freopen("set.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>a[i];
}
sort(a+1,a+m+1);
m=unique(a+1,a+m+1)-a-1;
dfs(n);
cout<<ans.size();
return 0;
}
}
int main(){return asbt::main();}
/*
562949953421312 10
2 3 5 7 11 13 17 19 23 29
*/
B. 忍者小隊
設 \(b_x=\sum_{i=1}^{n}[x|S_i]\)，可以調和級數求。于是有如果最小值存在則最大值為 \(b_x\)，否則最大值也不存在。
記值域為 \(V\)。注意到前七個質數的乘積就超過了 \(V\)，所以 \(k=1\) 時答案最多為 \({7\choose6}=7\)，顯然 \(k\) 更大時答案也不會超過 \(7\)。考慮枚舉每個答案是否可行。假設當前枚舉到了 \(t\)，設 \(f_x\) 表示選出 \(t\) 個數使它們的 \(\gcd=x\) 的方案數，則有：
\[f_x={b_x\choose t}-\sum_{i=2}^{\lfloor\frac{V}{x}\rfloor}f_{ix}
\]
于是若 \(f_x=0\) 則 \(t\) 不可行，否則可行。時間復雜度 \(O(7V\ln V)\)。
Code
#include<bits/stdc++.h>
#define ll long long
#define il inline
using namespace std;
namespace asbt{
const int maxn=3e5+5,mod=1e9+7,V=3e5,inf=1e9;
il int pls(int x,int y){
return x+y<mod?x+y:x+y-mod;
}
il void add(int &x,int y){
x=pls(x,y);
}
il int mns(int x,int y){
return x<y?x-y+mod:x-y;
}
il void sub(int &x,int y){
x=mns(x,y);
}
int n,m,a[maxn],fac[maxn],inv[maxn],tong[maxn],f[maxn],g[maxn],ans[maxn];
il int qpow(int x,int y=mod-2){
int res=1;
while(y){
if(y&1){
res=res*1ll*x%mod;
}
x=x*1ll*x%mod,y>>=1;
}
return res;
}
il void init(int n=V){
fac[0]=1;
for(int i=1;i<=n;i++){
fac[i]=fac[i-1]*1ll*i%mod;
}
inv[n]=qpow(fac[n]);
for(int i=n;i;i--){
inv[i-1]=inv[i]*1ll*i%mod;
}
}
il int C(int x,int y){
return x<y||y<0?0:fac[x]*1ll*inv[y]%mod*inv[x-y]%mod;
}
int main(){
freopen("sor.in","r",stdin);
freopen("sor.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
tong[a[i]]++;
}
for(int i=1;i<=V;i++){
for(int j=i;j<=V;j+=i){
g[i]+=tong[j];
}
}
init();
memset(ans,0x3f,sizeof(ans));
for(int t=1;t<=7;t++){
for(int i=V;i;i--){
f[i]=C(g[i],t);
for(int j=i<<1;j<=V;j+=i){
sub(f[i],f[j]);
}
if(f[i]){
ans[i]=min(ans[i],t);
}
}
}
for(int i=1;i<=m;i++){
if(ans[i]>=inf){
cout<<-1<<' '<<-1<<'\n';
}else{
cout<<ans[i]<<' '<<g[i]<<'\n';
}
}
return 0;
}
}
int main(){return asbt::main();}
浙公網安備 33010602011771號