【arc077f】AtCoder Regular Contest 077 F - SS
2024-10-08 01:32:24
题意
给你一个形如"SS"的串S,以及一个函数\(f(x)\),\(x\)是一个形如"SS"的字符串,\(f(x)\)也是一个形如"SS"的字符串。
\(x\)是\(f(x)\)的一个前缀,并且要让\(f(x)\)尽量短。
问在\(f^{10^{100}}(S)\)中,[L,R]中所有字符的出现次数。
\[字符集为小写字母,|S|<=100000,1<=L<=R<=1e18\]
解法
可以发现的是S只用考虑前一半,因为进行了许多次变换,已经后一半不在1e18的范围内。
首先我们第一步应该做的是去观察这个函数的变化规律。
通过最初几步的打表,
我们可以发现,设T是S的border,那么f(S)=ST
S->ST->STS->STSST->....
到这里已经相当明显。
这个变化呈现的是一个类似于斐波那契数列的变换。
所以我们可以模拟这个过程。
由于通过斐波那契的变换只需log(1e18)次就可以超过1e18的长度,
时间复杂度是\(O(log^2)\)的。
border的求法相当简单,
我们给串做一次KMP,然后Brd=n-Fail[n]
最新文章
- 数据库的Timeout
- js 比较好的博客
- Maven仓库搭建--nexus私服
- Java——新IO 缓冲区与Buffer
- 利用 ELK系统分析Nginx日志并对数据进行可视化展示
- 1742. Team building(dfs)
- And Then There Was One
- 开源项目AndroidUtil-采用Fragment实现TabHost
- 用MySQL创建数据库和数据库表
- div、span
- asp 操作 json
- 生成验证码JSP【复用代码】
- spring 多线程 写入数据库 和 写入 xml文件
- 其它综合-CentOS7 忘记root密码
- POJ--3974 Palindrome(回文串,hash)
- 如何启用小米手机5c的ROOT权限
- 潭州课堂25班:Ph201805201 第六课:散列类型,运算符优先级和逻辑运算 (课堂笔记)
- Android-创建启动线程的两种方式
- leetcode之二叉树的层序遍历
- ASP.NET Core使用Ping判断网络是否接通