AtCoder Regular Contest 064 F - Rotated Palindromes
2024-09-04 08:09:51
Problem Statement
Takahashi and Aoki are going to together construct a sequence of integers.
First, Takahashi will provide a sequence of integers a, satisfying all of the following conditions:
- The length of a is N.
- Each element in a is an integer between 1 and K, inclusive.
- a is a palindrome, that is, reversing the order of elements in a will result in the same sequence as the original.
Then, Aoki will perform the following operation an arbitrary number of times:
- Move the first element in a to the end of a.
How many sequences a can be obtained after this procedure, modulo 109+7?
Constraints
- 1≤N≤109
- 1≤K≤109
Input
The input is given from Standard Input in the following format:
N K
Output
Print the number of the sequences a that can be obtained after the procedure, modulo 109+7.
Sample Input 1
Copy
4 2
Sample Output 1
Copy
6
The following six sequences can be obtained:
- (1,1,1,1)
- (1,1,2,2)
- (1,2,2,1)
- (2,2,1,1)
- (2,1,1,2)
- (2,2,2,2)
Sample Input 2
Copy
1 10
Sample Output 2
Copy
10
Sample Input 3
Copy
6 3
Sample Output 3
Copy
75
Sample Input 4
Copy
1000000000 1000000000
Sample Output 4
Copy
875699961
用1-k填序列,序列可以左移n次变为回文
不考虑移位总共有k^(n/2)个回文,所以就是一个容斥问题了
若回文串的最小循环节长度为c,经过c次操作后,得到c个序列
当c为偶数时,重复数为一半,奇数时,无重复
所以这个问题就解决了,其循环节只可能是其因子
#include <bits/stdc++.h>
using namespace std;
const int N=,MD=1e9+;
int v[N],f[N];
int Pow(int x,int y)
{
int ans=;
for(;y;x=x*1LL*x%MD,y>>=)if(y&)ans=1LL*ans*x%MD;
return ans;
}
int main()
{
int n,k,tot=,ans=,i;
cin>>n>>k;
for(i=; i*i<n; i++)
if(n%i==)v[tot++]=i,v[tot++]=n/i;
if(i*i==n)v[tot++]=i;
sort(v,v+tot);
for(int i=; i<tot; i++)
{
f[i]=Pow(k,(v[i]+)/);
for(int j=; j<i; j++)if(v[i]%v[j]==) f[i]=(f[i]-f[j])%MD;
if(v[i]&) ans=(ans+1LL*v[i]*f[i])%MD;
else ans=(ans+v[i]*1LL*Pow(,MD-)%MD*f[i])%MD;
}
cout<<(ans+MD)%MD;
}
最新文章
- Android入门(一)
- 0512 Scrum 项目3.0
- ThinkPHP实现移动端访问自动切换主题模板
- X-UA-Compatible是神马
- 自定义NSLog宏输出
- Educational Codeforces Round 7 D. Optimal Number Permutation 构造题
- 【译】 AWK教程指南 8处理多行数据
- Quartz 之 windowService
- Finding the Longest Palindromic Substring in Linear Time
- 一个简单的mfc单页界面文件读写程序(MFC 程序入口和执行流程)
- pull类型消息中间件-消息发布者(一)
- [转载] Hadoop MapReduce
- 使用Jenkins时,如果GIT_COMMIT无变化,跳过构建
- 书上关于*(p++)表达式的几种变形形式的思考题
- odoo开发笔记--取消正在升级中模块
- ida脚本函数
- html5 ajax多图片可预览上传图片
- GoogLeNetv4 论文研读笔记
- jQuery 动态加载下拉框选项(Django)
- redis cluster应用连接(password)
热门文章
- ./theHarvester.py -d baidu.com -l 100 -b google
- UML的九种模型图
- LibreOJ #2037. 「SHOI2015」脑洞治疗仪
- kubernetes-核心概念及创建应用(六)
- centos7中文显示为小方块~~啊啊啊 求大佬们解答
- mtDNA|ctDNA|cpDNA|
- javaweb基础(4)_http协议
- Codeforces Round 513 (Div.1+Div.2)
- eclipse 中main()函数中的String[] args如何使用?通过String[] args验证账号密码的登录类?静态的主方法怎样才能调用非static的方法——通过生成对象?在类中制作一个方法——能够修改对象的属性值?
- C# 调用腾讯地图WebService API获取距离(一对多)