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

NOIP2020 T2

给定长度为 \(n(1 \le n \le 2^{20})\) 的字符串 \(s\),问有多少种合法的拆分方式?一种合法的拆分方式:

  • \(s = (AB)^iC(i > 0)\)其中 \(A,B,C\) 为非空字符串,\((AB)^i\)\(i\)\(AB\) 拼接的结果。
  • \(F(A) \le F(B)\) \(F(s)\) 表示 \(s\) 中出现奇数次的字符数。

先忽略第二个条件。显然可以把 \(AB\) 看成一个整体(题目给了很强的提示),枚举 \(AB\) 的长度 \(len\),用 hash 判断每个 \(i\) 是否可行。

由调和级数可知,至多由 \(n \log n\)\(i\)。每个 \(i\)\(len - 1\) 种选法。

接下来考虑第二个条件,可以预处理出 \(s\) 有段后缀的 \(F_i\) ,然后将长度为 \(1 \sim len - 1\)\(F\) 丢到数组里(表示 \(A\) 的选法),查询 \(F_{i\cdot len + 1}\) 对应的贡献即可。

因为 \(F \le 26\),直接暴力加贡献即可。(否则还要个树状数组,时间复杂度是 \(O( n\log n\log26)\))。

时间复杂度:\(O(n (\log n + 26))\)

注意下常数能过,似乎有 \(O(n)\) 的扩展 KMP 做法。

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

相关文章:

  • Alex-VGG3
  • 第二章日志分析-redis应急响应
  • 第一章 应急响应- Linux入侵排查
  • 浏览器多开的方法
  • 10月17号
  • 19. 删除链表的倒数第 N 个结点
  • Day13
  • 第一章日志分析-mysql应急响
  • 操作系统应用构建(十二)RustDesk 用户服务器搭建——东方仙盟筑基期
  • python-IDLE定制界面大小
  • 高级语言程序设计第1次作业
  • Maui:通过附加属性将命令绑定到事件
  • 超好用的浏览器多开小工具!轻松管理多个账号,可以无限制使用其他插件
  • 微服务组件-Eureka 科技详解
  • 新学期每日总结(第10天)
  • List.subList() 返回值为什么不能强转成 ArrayList
  • 奶奶都能看懂的 C++ —— 手把手指针
  • 10/17
  • CSP-2024 T4
  • 02-类与对象课后作业
  • NOIP2021 T2
  • 从零开始实现简易版Netty(九) MyNetty 实现池化内存的线程本地缓存
  • 杏帘招客饮,在望有山庄。
  • 洛谷 P8512
  • 从libtorch_cuda.so中提取某个函数的sass汇编指令
  • 【题解】成外友谊赛
  • 小程序商城客服系统
  • ubuntu 主机创建虚拟 ip,应对容器内部配置了宿主固定 ip,宿主迁移网络环境后容器报错
  • 2025权威报告:微信编辑器排版Top 10工具推荐(全链路解决方案)
  • 洛谷 P10149