当前位置: 首页 > news >正文

10.8 CSP-S模拟27 改题记录

HZOJ

写在前面

国庆后第一套。大概就是倒数第二吧。但是无所谓逃过了二调。四道数学/计数,呵呵哈哈哈哈哈哈。讨厌容斥反演。从今天开始祈祷抄手皮和恩欧挨批不要考这种玩意,或者考也考我会做的(?)。天气一下子冷了,好像今年也没有太感受到秋天。。。

A. 喜剧的迷人之处在于

题意是给出一个\(a\) 和区间\(l-r\),求区间内是否存在一个\(b\) 使得\(a\times b\) 是完全平方数。如果存在,最小化其取值。

挺显然的做法。就是把\(a\) 分解质因数,将不是偶数次的因数相乘即为最小的\(b\),如果\(b\) 比区间大则无解,如果\(b\) 比区间小就乘上一个能使积不小于\(l\) 的完全平方数再判断是否在区间内。

既然做法显然那么为什么还要写呢?大概就是挂如分了哈哈哈。大概就是做除法没有将整数转化为浮点数吧哈哈哈。竟然只挂了20pts。

代码就不放了,没啥意义。

B. 镜中的野兽

神仙题。题意是给出一个不可重集\(S\) 的大小和 \(gcd(S)+lcm(S)\) 的值\(m\),求问\(S\) 可能的元素构成。

思路算容易出,赛时想到的是通过某种方法确定\(lcm\)\(gcd\),确定某个质因数的取值次幂的上界和下界,对于每个质因数,要有至少分别一个数满足上界和下界,然后动用组合数学就行了。然后写写化化发现样例都过不去。打表一看:没有满足不可重的限制。然后一头扑在容斥怎么写上inf分钟,最后喜提5pts。

先解决第一个问题:如何确定\(gcd\)\(lcm\)。由于\(gcd|lcm\),所以\(gcd|m\),枚举\(m\)的因数作为\(gcd\)即可,枚举复杂度\(O(\sqrt(m))\)

求解答案时,可以先将\(lcm\) 除以\(gcd\),不用再额外确定下界,某一个因数取\(0\) 便是下界。然后状压枚举某个因数是否有达到上下界的情况,统计方案数,容斥掉即可。对于求方案数,就是在所有方案中选取\(n\) 个。虽然\(n\) 比较大,但是方案数和范围比较小,所以可以通过组合数公式求取。

(写完才发现好像可以勉强理解了)

代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=4e4+10,maxm=1e6+10;
bool isnp[maxn]={1,1};
int cnt,prime[maxn],jc[maxm],ny[maxm],n,m,p;
inline void getprime(){for(int i=2;i<=4e4;i++){if(!isnp[i]) prime[++cnt]=i;for(int j=1;j<=cnt&&prime[j]*i<=4e4;j++){isnp[i*prime[j]]=1;if(i%prime[j]==0) break;}}
}
inline int qpow(int x,int y,int mod){if(!x) return 0;int res=1;while(y){if(y&1) res=1ll*x*res%mod;x=1ll*x*x%mod;y>>=1;}return res;
}
inline int C(int x,int y,int mod){if(x<y) return 0;return 1ll*jc[x]*ny[y]%mod*ny[x-y]%mod;
}
inline int dd(int x){int w=x;vector<int> ys,gs;for(int i=1;prime[i]*prime[i]<=w;i++)if(w%prime[i]==0){ys.emplace_back(prime[i]);gs.emplace_back(0);while(w%prime[i]==0) ++gs.back(),w/=prime[i];}if(w>1) ys.emplace_back(w),gs.emplace_back(1);int siz=ys.size(),ans=0;for(int s=0;s<(1<<(siz<<1));s++){int x=1;for(int i=0;i<=siz-1;i++){int u=(s>>i)&1,v=(s>>(i+siz))&1;if(u+v>gs[i]+1){x=0;break;}else x=1ll*x*(gs[i]+1-u-v)%p;}int t=__builtin_popcount(s);if(t&1) ans=(ans-C(x,n,p))%p;else ans=(ans+C(x,n,p))%p;if(!s&&x<n) return 0;}return ans;
}
int main(){getprime();int ans=0;cin>>n>>m>>p;if(m==1) cout<<0,exit(0);else if(n==1) cout<<(m%2==0),exit(0);jc[0]=ny[0]=1;for(int i=1;i<=1e6;i++) jc[i]=1ll*jc[i-1]*i%p,ny[i]=qpow(jc[i],p-2,p);for(int i=1;i*i<=m;++i)if(m%i==0){int gcd=i,lcm=m-i;if(gcd<lcm){lcm/=gcd;ans=(ans+dd(lcm))%p;}if(i*i==m) break;gcd=m/i;lcm=m-i;if(gcd<lcm){lcm/=gcd;ans=(ans+dd(lcm))%p;}} cout<<(ans%p+p)%p;return 0;
}

C. 我愿相信由你所描述的童话

题意是给定一个序列,求问该序列有多少个子序列满足以某个点为界,子序列所有数二进制表示都是该点的子集,且在某一方向上远离该点的数是靠近该点的数的子集。

感觉像个求类似于单峰的东西。因为T2耗了太多时间所以就打了个\(O(n^2)\) 的暴力。然后过不了样例,然后发现这题和T2是亲兄弟,这题也要容斥。然后写了半天还是败给了容斥。

首先\(O(n^2)\) 的复杂度不可过。\(O(n^2)\) 来自于状态的转移。分析一下,修改一个点的值是\(O(1)\) 的,对于某个点要进行的查询是\(O(n^2)\) 的,好像无法优化。但对于这道题,对于某个点进行的查询也可以\(O(n2^m)\) 完成,因为\(m\) 值域较小。由于查询操作与修改操作类似,所以考虑平衡复杂度,将一部分查询的操作放到修改做。具体做法就是查询时枚举前一半二进制的子集,修改时枚举后一半二进制的超集,这样查询操作和修改操作都是\(O(n2^{\frac{m}{2}})\) 的了,可以通过。

然后重头戏是容斥。本题重复讨论的情况出现在某个值作为最大集合出现时,多个最大值连续出现的情况。本题的容斥其实比上题好想(虽然我还是没想出来),某个点对答案贡献的方案数就该是该点对所有前驱与后继组合的方案数减去以该点相同值为前驱与所有后继组合的方案数。

代码
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7,maxn=3e5+10,len=20;
int n,m;
int le[maxn],ri[maxn],k[maxn];
int suml[maxn*10],sumr[maxn*10],delta[maxn],sum[maxn*10];
inline void qryl(int lv,int x,int l,int r){if(l>r){le[lv]=(le[lv]+suml[x])%mod;return;}qryl(lv,x,l+1,r);if((x>>(l-1))&1) qryl(lv,x^(1<<(l-1)),l+1,r);
}
inline void updatel(int lv,int x,int l,int r){if(l>r){suml[x]=(suml[x]+le[lv])%mod;return;}updatel(lv,x|(1<<(l-1)),l+1,r);if(!((x>>(l-1))&1)) updatel(lv,x,l+1,r);
}
inline void qryr(int lv,int x,int l,int r){if(l>r){ri[lv]=(ri[lv]+sumr[x])%mod;return;}qryr(lv,x,l+1,r);if((x>>(l-1))&1) qryr(lv,x^(1<<(l-1)),l+1,r);
}
inline void updater(int lv,int x,int l,int r){if(l>r){sumr[x]=(sumr[x]+ri[lv])%mod;return;}updater(lv,x|(1<<(l-1)),l+1,r);if(!((x>>(l-1))&1)) updater(lv,x,l+1,r);
}
int main(){
//	freopen("ex_belief5.in","r",stdin);ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cin>>n>>m;for(int i=1;i<=n;++i) cin>>k[i];int ans=0;for(int i=1;i<=n;++i){qryl(i,k[i],1,m>>1);delta[i]=sum[k[i]];++le[i];sum[k[i]]=(sum[k[i]]+le[i])%mod;updatel(i,k[i],(m>>1)+1,m);}for(int i=n;i>=1;--i){qryr(i,k[i],1,m>>1);++ri[i];updater(i,k[i],(m>>1)+1,m);}for(int i=1;i<=n;++i) ans=(ans+1ll*(le[i]-delta[i])*ri[i]%mod)%mod;cout<<(ans%mod+mod)%mod;return 0;
}

D. Baby Doll

不会,咕了。

http://www.hskmm.com/?act=detail&tid=27523

相关文章:

  • 《可复制的领导力》
  • 经营分析会 - 智慧园区
  • 自动评估问答模型的技术突破
  • Ivanti EPM移动版12.5.0.0身份验证绕过漏洞分析与利用
  • 运行Udacity的MPC控制项目指南(project_10)在Ubuntu 18.04环境下
  • 深入解析:Java 将 PDF 转换为 PDF/A:数字文档归档的基石
  • 入门正当时!MQTT协议轻量简洁,但应用绝不简单
  • 英语阅读
  • CF1832D2 Red-Blue Operations (Hard Version) 模拟赛题目分析
  • 网络流最小割,无向图建图法,求最小割点转换求最小割边
  • 实验1 C语言开发环境使用和数据类型、运算符、表达式
  • 深度学习概述 - -一叶知秋
  • 烧录神器来了!量产工具使用教程,新手也能秒懂
  • 看论文随笔Incendio: Priority-Based Scheduling for Alleviating Cold Start in Serverless Computing
  • C#性能优化基础:内存诊断(dump)
  • 2025年企业级LLM内容安全防护指南:鉴冰AI FENCE流式网关技术深度解析
  • 完整教程:FPGA学习笔记——图像处理之亮度调节(Gamma)
  • Kubernetes Ingress:管理集群外部访问的入口网关
  • 搜索选讲
  • vue打包的项目,从根目录进去路由可访问,浏览器直接打开这个路由不可访问
  • IObit Uninstaller一款强大的卸载工具!IObit Uninstaller卸载工具,IObit Uninstaller下载安装教程
  • 网络配置不再难:4G/Wi-Fi/以太网/虚拟网卡全指南
  • 计算几何
  • 2025开关按钮厂家最新推荐榜:开关按钮,带灯开关按钮,防水开关按钮,防爆开关按钮,防腐开关按钮等全种类覆盖,高品质设计与卓越性能口碑之选
  • 一种排查java.lang.OutOfMemoryError: Metaspace的方法
  • First Blog Post
  • 本站点即将在2025年改变研究方向和目标
  • 实用指南:12_OkHttp初体验
  • (AE)Adobe After Effects 2025 视频后期制作软件!安装包永久免费免激H解锁版下载与图文详细安装教程!!
  • Postgresql主从配置