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

ABC325EF 题解

D - Ulam-Warburton Automaton

待补。

E - Count Sequences 2

多重集排列数板子,典得不能再典的问题,这都能放来当比赛题的?

\(n = \sum C_i\),通常使用的公式为

\[ans = \dfrac{n!}{\prod_{i = 1}^{N} C_{i}!} \]

但是模数不是质数,不一定存在乘法逆元,所以不能使用带除法的式子。使用另一个公式就好了:

\[ans = \dbinom{n}{C_1}\dbinom{n - C_1}{C_2} \cdots \dbinom{n - C_1 - C_2 - \cdots - C_{N - 1}}{C_N} \]

用杨辉三角递推式可以在 \(O(n^2)\) 时间内预处理组合数,且不需要除法,于是就做完了。

参考代码

(但是赛时忘了第二个公式,想了半天)

F - Inserting Process

看到 \(N\) 很小,容易想到把每个子序列设为一个状态,这样状态数为 \(2^{N}\)。正着加字符是困难的,因为我们难以快速判定,一个子序列插入一个字符得到的字符串是不是原串的子序列。套路性地倒着考虑,即研究有多少种方法可以把原串删为空串。

一个简单的想法是:用下标序列 \((1, 2, \cdots, n)\) 的子序列 \((p_1, p_2, \cdots, p_m)\) 表示子序列 \(t = s_{p_1}s_{p_2}\cdots s_{p_m}\),枚举删去的字符来转移。问题在于:一个字符串删去不同位置的字符,可能得到相同的字符串,例如 \(\tt{aab}\) 删去第一个字符或第二个字符得到的字符串都是 \(\tt{ab}\),这样就算多了。

于是我们要解决的问题是:如何使子序列的表示方式唯一?例如对于 \(s = \tt{aab}\),我们希望子序列 \(t = \tt{ab}\) 只有一种表示方式。实际上,在转移的过程中,简单地加上一条限制即可:如果出现连续相同的字符,只能删除最右边的字符。那么,\(\tt{aab}\) 只能删除第二个字符得到 \(\tt{ab}\),这样两个子序列之间的转移就唯一了,因而解决了算重的问题。

另外多说一句,我们确实给每个子序列找到了唯一的表示方式:如果一个子序列的表示方式不唯一,我们总是取字典序最小的那个。例如 \(\tt{ab}\)\(\tt{aab}\) 中的表示方式有两个:\((1, 3)\)\((2, 3)\),而我们只会转移到字典序较小的 \((1, 3)\)。这不难感性理解,严谨证明可能需要使用一下数学归纳法,但我们最好不要陷入抽象的形式化语言中。

总结:对于有重复贡献的问题,考虑给每个对象确定一个唯一的表示方式。这种思想是相当常见的。

参考代码

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

相关文章:

  • Win11 安装 Python
  • mysql的单表多大要考虑分库分表
  • 2025 采购传感器不踩坑!国内传感器优秀厂家清单:解决精度,防爆,极端环境难题
  • sg.有没有一个可视化辅助设计pysimplegui布局的小工具?
  • 无刷电机速度闭环控制
  • sg.如何使用PySimpleGUI调试器实时监控变量
  • 微信小程序云开发 授权手机号快捷登陆
  • newDay05
  • AtCoder Beginner Contest 425 ABCDEF 题目解析
  • sg.如何使用PySimpleGUI调试器窗口
  • 对话汇总:从东方哲学到可计算架构的演进
  • 25.9.27 继续MyBatis
  • MoeCTF 2025 二进制漏洞审计:boomboom_revenge
  • 集训总结(九)
  • 完整教程:操作系统之初识Linux
  • XJSOJ优化(Stylus脚本)
  • 使用mpm-itk让Apache以不同用户身份运行的完整指南
  • sg.如何打开PySimpleGUI调试器窗口?
  • 第6篇、Flask 表单处理与用户认证完全指南:从零到实战
  • 威联通 NAS Docker 容器更新详解:从备份、推送到重建的全流程指南
  • parameter和defparam的简单用法
  • 9.27学习笔记
  • 开学日记
  • 生活随笔
  • UNIQUE VISION Programming Contest 2024 Autumn (AtCoder Beginner Contest 425)
  • 论文解读-《Less is More on the Over-Globalizing Problem in Graph Transformers》 - zhang
  • 作业2
  • NOIP模拟赛 十八
  • loguru 日志库快速入门
  • lca学习笔记