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

2025.10

Todolist:118e 的形式化理解方法,做一下 abc426,感觉有点难度,abc425f 的 poly 做法,149d 的 universal 做法,有交合并的复杂度证明,1554e 更快的做法。

[ARC121E] Directed Tree

考虑容斥转化为 \(a_u\)\(u\) 的祖先,这个还是不好算。\(a_u\)\(u\) 的祖先也就是 \(u\)\(a_u\) 的子树内,也就是逆排列的限制是子树。

钦定一个 \(S\),方案数是 \((-1)^|S| (n-|S|)! \prod_{i \in S}siz_i\),其中被钦定的点大小为 \(0\) 否则为 \(1\),也就是别的说的 \(siz-t\)。正确道理就是向上合并的过程中各个子树独立了,同时选自己符合题目中的限制,因此钦定不合法时不能选自己要 \(-1\),同时钦定了这个点因此子树内的点数就是钦定数 \(-1\),符号反过来就是 \(+1\) 恰好抵消。

改成树形 dp,设 \(f_{x,i}\) 表示 \(x\) 子树内 \(|S|=i\) 的容斥系数方案数和,先背包转移,再考虑钦定点就是 \(f_{x,i}=f_{x,i}-f_{x,i-1} \times (siz_x-i)\),这里 \(siz\) 是普通 \(siz\),防止重复更新要倒着算。

[ARC149D] Simultaneous Sugoroku

直接上大暴力,那就是分成 \(<0,>0\) 的部分加一个数,发现是值域有交平衡树合并。注意相同数要合并(但他们仍然存在,因此要用并查集表示指向了哪个数)否则复杂度会错,我也不知道为什么。

CF1554E.You

先来一遍莫反转化为计算倍数的形式。

实际上这样可能并不好做。首先在点上这个限制会非常麻烦,尝试用边描述限制,发现每条边只能给两侧的某一个端点做贡献,大概是一个给边定向的过程,指向的点就是这条边贡献到的 \(a\)

由于我们考虑的是 \(a\) 而不是删除点的序列,所以只需要考虑定向是否和 \(a\) 构成双射即可,每次根据 \(a=0/1\) 给叶子定向后剥叶子即可得到唯一的定向因此是双射,答案总数是 \(2^{n-1}\)

现在考虑 \(\gcd\) 的事,我们喜欢剥叶子,知道叶子的 \(a\) 值只能是 \(0/1\),如果 \(k>1\) 至少要求所有的点都是 \(k\) 的倍数,那么叶子必须是 \(0\),定好这些边的向后剥去她们,考虑新的叶子,因为是 \(k\) 的倍数所以大概也能定出向,但是不能保证是 \(k\) 的倍数了,也就是,父亲边怎么定向都不对,那这个 \(k\) 就达不到,否则也是唯一的方案。

剥叶子表现为拓扑排序,这样总复杂度是 \(\mathcal{O}(n^2)\),有 \(\gcd(a,b)=\gcd(a,a+b)\),所以原式的 \(\gcd\) 可以再添上一个 \(\sum a\) 项,这项一定是 \(n-1\),因此 \(k\) 必须是 \(n-1\) 的因数,这就是 \(\mathcal{O}(n \sqrt n)\) 的了。

还有判素因子的优化,但无人在意啊!

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

相关文章:

  • PCIe扫盲——物理层逻辑部分基础(一)
  • 仅需3%训练数据的文本归一化技术
  • 价值原语博弈协议:价值原语共识锚定原则
  • 实用指南:工作流引擎-16-开源审批流项目之 整合Flowable官方的Rest包
  • 25fall做题记录-October - Amy
  • 嗯嗯
  • PCIe扫盲——AckNak 机制详解(二)
  • ASP.NET Core SignalR 身份认证集成指南(Identity + JWT) - 详解
  • utorrent 2.2.1
  • 2025热缩管厂家 TOP 企业品牌推荐排行榜,氟橡胶,双壁,线缆标识,防滑花纹,DR 耐油橡胶,PVDF,标识,航插用,军用热缩管公司推荐!
  • 市场交易反心理特征之八:劣仓驱逐良仓
  • 做题笔记18
  • 2025桩基检测机构最新企业咨询服务推荐排行榜,海上桩基检测,水上桩基检测服务推荐这十家公司!
  • 算法坑点
  • [省选联考 2025] 图排列 题解
  • Windows下安装并采用kubectl查看K8S日志
  • 实用指南:UV 包管理工具:替代 pip 的现代化解决方案
  • C/C++与Java、Python、Go在各个阶段的区别
  • 古典密码之凯撒密码
  • vi/vim文本编辑器
  • AI一周资讯 250926-251005
  • B3869 [GESP202309 四级] 进制转换-题解
  • 物理
  • springcloud gateway Error creating bean with name bootstrapImportSelectorConfiguration:
  • 完整教程:PyCharm接入DeepSeek,实现高效AI编程
  • Nginx的核心功能及实现
  • 2025焚烧炉厂家权威推荐,技术实力与市场口碑深度解析
  • 高考加油!UI界面生成器! - 教程
  • UnityShader入门精要-系统语义与函数体
  • 从价值博弈到价值原语博弈的跃迁:降维解析与升维求解的工程实现——声明Ai研究