Rusty String
2024-08-26 06:53:22
题意:
给定一个含有两种字符'V','K'以及?的字符串,问该串可能的循环节。
解法:
首先如果对于$d$,我们有不存在 $(j-i) | d$ 且 $S_i = 'V', S_j = 'K'$ 的,那么 $d$ 为1循环节。
这样考虑对于每一个 $d$ 求出 $j-i = d$ 的 $S_i = 'V', S_j = 'K'$ 是否存在,然后 $O(nlogn)$ 筛一遍即可。
求 $j - i = d$ 的有
$$c_{n - i} = \sum_{0 \leq j \leq i} { a(j) b(n-i+j-1) }$$
$$c_{n - i} = (reva \otimes b)_{2n-i-1} = \sum_{0 \leq t \leq 2n-i-1}{ reva_t b_{2n-i-1-t} }$$
标准卷积,DFT即可。
#include <bits/stdc++.h> #define PI acos(-1) const int N = ; using namespace std; struct EX
{
double real,i;
EX operator+(const EX tmp)const{return (EX){real+tmp.real, i+tmp.i};};
EX operator-(const EX tmp)const{return (EX){real-tmp.real, i-tmp.i};};
EX operator*(const EX tmp)const{return (EX){real*tmp.real - i*tmp.i, real*tmp.i + i*tmp.real};};
}; int R[N<<]; void DFT(EX a[],int n,int tp_k)
{
for(int i=;i<n;i++) if(i<R[i]) swap(a[i],a[R[i]]);
for(int d=;d<n;d<<=)
{
EX wn = (EX){cos(PI/d), sin(PI/d)*tp_k};
for(int i=;i<n;i += (d<<))
{
EX wt = (EX){,};
for(int k=;k<d;k++, wt = wt*wn)
{
EX A0 = a[i+k], A1 = wt * a[i+k+d];
a[i+k] = A0+A1;
a[i+k+d] = A0-A1;
}
}
}
if(tp_k==-)
for(int i=;i<n;i++) a[i] = (EX){a[i].real/n, a[i].i/n};
} EX A[N<<],B[N<<],C[N<<];
char S[N];
int n;
bool del[N],ans[N]; void calc(char ch1,char ch2,int tot)
{
for(int i=;i<tot;i++) A[i] = B[i] = (EX){,};
for(int i=;i<n;i++) if(S[i]==ch1) B[i] = (EX){,};
for(int i=;i<=n;i++) if(S[n-i]==ch2) A[i] = (EX){,};
DFT(A,tot,);
DFT(B,tot,);
for(int i=;i<tot;i++) C[i] = A[i]*B[i];
DFT(C,tot,-);
for(int i=;i<n;i++)
{
int tmp = (int)(C[*n-i-].real+0.5);
if(tmp) del[i] = ;
}
} int main()
{
int T;
cin>>T;
while(T--)
{
scanf("%d%s",&n,S);
int L = ,tot;
while((<<L)<n+n) L++;
tot = (<<L);
for(int i=;i<tot;i++) R[i]=(R[i>>]>>)|((i&)<<(L-));
for(int i=;i<n;i++) del[i] = , ans[i+] = ;
calc('V','K',tot);
calc('K','V',tot);
for(int i=n-;i>=;i--) if(!del[i]) ans[n-i-] = ;
ans[n] = ;
int cnt = ;
for(int i=;i<=n;i++)
{
for(int j=i+i;j<=n;j+=i) ans[i] &= ans[j];
if(ans[i]) cnt++;
}
printf("%d\n",cnt);
for(int i=;i<=n;i++) if(ans[i]) printf("%d ",i);
printf("\n");
}
return ;
}
最新文章
- SQLExecption:Operation not allowed after ResultSet closed解决办法
- java 杂物间 (一) Mybatis
- 【ASP.NET MVC 】让@Ajax.ActionLink获取的数据不进Cache
- Android --资料集合
- ACM题目————The partial sum problem
- 【解决】U盘装系统(Win7/Win8)&; 装双系统
- jQuery validate运作流程以及重复提示错误问题
- lesson2:java阻塞队列的demo及源码分析
- poj 3233 Matrix Power Series
- CodeForces 135C C. Zero-One
- javascript创建类的6种方式
- 【C语言】字符串模块
- Dapper源码学习和源码修改
- JavaScript基础学习(六)&mdash;函数
- 性能测试中TPS上不去的几种原因浅析
- PHP之单例模式
- [Educational Round 3][Codeforces 609F. Frogs and mosquitoes]
- 宝岛探险,DFS&;BFS
- Hammer.js 移动端手势库,多点触控插件
- DOS中命令的格式
热门文章
- 关于ASP.NET MVC中Response.Redirect和RedirectToAction的BUG (跳转后继续执行后面代码而不结束进程)以及处理方法
- hdu 5316 Magician 线段树
- WPF 的 MVVM
- Tomcat服务器改主页 &; jeesite框架改首页
- Windows App开发之集合控件与数据绑定
- kubernetes调度之污点(taint)和容忍(toleration)
- HDFS 原理、架构与特性介绍
- java线程中断[interrupt()函数] (转载)
- VC ++6.0英文版常用菜单使用参考【转载整理】
- spring applicationContext.xml详解及模板