ARC 064 F-Rotated Palindromes
2024-09-06 20:46:41
题意
问有多少个长度为 \(N\) 且字符集大小为 \(K\) 的字符串可以通过回文串旋转 (把第一个字符移到最后)若干次得到。\(N,K\le 10^9\)
做法
设\(f_i\)为最小周期为\(i\)的回文串个数
有\(f_i=K^{\left\lceil\frac{i}{2}\right\rceil}-\sum\limits_{j|i,j\neq i}f_{j}\)
若\(i%N\neq 0\),可以通过是回文串的性质,将其调整为更小的\(i\)或更大的\(i\),所以这里我们只考虑\(i|N\)
一个周期为\(i\),则可表示本质不同的\(i\)个串
若周期\(i\)为偶数,移位\(\frac{i}{2}\)后也是一个周期为\(i\)的回文串,所以会被统计两次
故:\[Ans=\sum\limits_{d|N,d~is~odd}f_d\cdot d+\frac{1}{2}\sum\limits_{d|N,d~is~even}f_d\cdot d\]
直接暴力是可过的
最新文章
- angular源码分析:angular中脏活累活的承担者之$interpolate
- windows shell api SHEmptyRecycleBin 清空回收站
- CSUOJ_1001
- ng-style 的坑 - 对性能的影响
- [HTML5]原生事件绑定和jquery动态事件绑定的区别
- spring事务学习(转账案例)(一)
- aspx控件属性
- OC6_目录及文件的创建
- Oracle SQL Developer 操作
- [ES6] Object.assign (with defaults value object)
- js拼音排序
- spring InitializingBean和DisposableBean init-method 和destroy-method @PostConstruct @PreDestroy
- 解压文件出错解决方法(invalid compressed data--format violated)
- Python基础:一、编程语言分类
- The perception and large margin classifiers
- 【JS加密库】SJCL :斯坦福大学JS加密库
- PHP eval函数
- 二叉树前中后/层次遍历的递归与非递归形式(c++)
- c++包管理工具conan
- 20145202马超 2016-2017-2 《Java程序设计》第8周学习总结