文档章节

BZOJ3457 : Ring

o
 osc_t4d5tw3o
发布于 2018/03/11 03:05
字数 585
阅读 27
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

根据Polya定理:

\[ans=\frac{\sum_{d|n}\varphi(d)cal(\frac{n}{d})}{n}\]

其中$cal(n)$表示长度为$n$的无限循环后包含$S$的串的数量。

对于$cal(n)$的计算,考虑用总方案数$2^n$减去单次循环内不包含$S$的方案数。

枚举进入循环时与$S$的KMP指针$k$,然后设$f[i][j]$表示考虑前$i$个位置,KMP指针为$j$的方案数,最终结果为$f[n][k]$。

转移可以用矩阵$G$表示,预处理出$G$的$2^0,2^1,...,2^{\log n}$次方,那么每次计算$cal(n)$只需要进行$O(k\log n)$次$O(k^2)$的矩阵乘向量。

总时间复杂度$O(d(n)k^3\log n)$。

 

#include<cstdio>
#define rep(i) for(int i=0;i<m;i++)
const int N=35,P=1000000007;
int n,m,i,j,k,nxt[N],g[N][2],e[N][N][N],c[N][N],f[N],h[N],ans;char a[N];
inline void mul(int a[][N],int f[][N]){
  rep(i)rep(j)c[i][j]=0;
  rep(i)rep(j)if(a[i][j])rep(k)if(a[j][k])c[i][k]=(1LL*a[i][j]*a[j][k]+c[i][k])%P;
  rep(i)rep(j)f[i][j]=c[i][j];
}
inline void mulv(int a[][N]){
  rep(i){
    h[i]=0;
    rep(j)if(f[j]&&a[i][j])h[i]=(1LL*f[j]*a[i][j]+h[i])%P;
  }
  rep(i)f[i]=h[i];
}
inline int phi(int n){
  int t=1;
  for(int i=2;i<=n/i;i++)if(n%i==0){
    t*=i-1,n/=i;
    while(n%i==0)t*=i,n/=i;
  }
  if(n>1)t*=n-1;
  return t;
}
inline int po(int a,int b){int t=1;for(;b;b>>=1,a=1LL*a*a%P)if(b&1)t=1LL*t*a%P;return t;}
inline int cal(int n){
  int t=0;
  for(int i=0;i<m;i++){
    rep(j)f[j]=i==j;
    for(int j=0;(1LL<<j)<=n;j++)if(n>>j&1)mulv(e[j]);
    t=(t+f[i])%P;
  }
  return(po(2,n)-t+P)%P;
}
int main(){
  scanf("%d%d%s",&n,&m,a+1);
  for(i=1;i<=m;i++)a[i]=a[i]=='R';
  for(i=2;i<=m;nxt[i++]=j){
    while(j&&a[j+1]!=a[i])j=nxt[j];
    if(a[j+1]==a[i])j++;
  }
  rep(i)for(j=0;j<2;j++){
    for(k=i;k&&a[k+1]!=j;k=nxt[k]);
    if(a[k+1]==j)k++;
    g[i][j]=k;
  }
  rep(i)for(j=0;j<2;j++)e[0][g[i][j]][i]++;
  for(i=1;(1LL<<i)<=n;i++)mul(e[i-1],e[i]);
  for(i=1;i<=n/i;i++)if(n%i==0){
    ans=(1LL*phi(i)*cal(n/i)+ans)%P;
    if(i*i!=n)ans=(1LL*phi(n/i)*cal(i)+ans)%P;
  }
  ans=1LL*ans*po(n,P-2)%P;
  return printf("%d",ans),0;
}

  

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
ntop 2016 路线图

ntop 2016 路线图 2015年是一个充满活力的年份,我们得以完善工具,为社区提供更好的服务。 2016年计划如下: 100 Gbit 正如在2015年我们已经在PF_RING 中为40 Gbit提供了支持,2016年将为100...

RiboseYim
2016/02/08
793
0
【转载】自制4412底板自动进入SD卡更新模块

转载自迅为论坛:http://www.topeetboard.com 参考平台:迅为iTOP-4412开发板 问题如下:在自制的底板上,当SD卡插在板子上开机时,会自动进入Updating模式,如果SD卡有sdupdate文件夹并且有...

歌之王子殿下
2017/02/15
202
0
高性能的网络应用的C++库--Herm

Herm是一套快速开发高性能的网络应用的C++库。比如开发网络游戏、即时通信、流媒体、文件下载、P2P等基于TCP/IP网络应用。(此项目已经不存在) Herm包括三个组件: (1)Utilities 最基础的...

匿名
2010/10/31
1W
0
分布式JSON对等协议--TeleHash

TeleHash 是一个新的用来实时和去中心化的JSON交互协议,可让应用在网络的边界直接进行连接。受益于 TeleHash,应用程序之间可高效的进行路由和分发小的数据。 示例: // basic Telex with ...

匿名
2010/05/22
1.3K
0
Ajax的源码编辑器--Ymacs

Ymacs是一个为程序员提供的可扩展的AJAX文本编辑器。它与Emacs类似:它支持多个缓冲区,分割帧,动态完成,多个按键,和Emacs一样撤消队列和kill ring。当然,Emacs的一样的,所有的键绑定。...

匿名
2009/12/15
1.2K
0

没有更多内容

加载失败,请刷新页面

加载更多

深入分析ES存储原理

es写数据 es写数据的过程 1、客户端选择一个 node 发送请求过去,这个 node 就是 coordinating node(协调节点)。 2、coordinating node 对 document 进行路由,将请求转发给对应的 node(有...

tankXiao
2分钟前
0
0
【1121】shell(下)

【1121】shell(下) 5.39 函数 5.40 shell 数组 数组赋值 数组的删除 数组分片 数组替换 5.39 函数 函数就是把一段代码整理到了一个小单元中,并给这个小单元起一个名字,当用到这段代码时直...

飞翔的竹蜻蜓
3分钟前
0
0
在JavaScript中定义枚举的首选语法是什么? [关闭]

问题: What is the preferred syntax for defining enums in JavaScript? 在JavaScript中定义枚举的首选语法是什么? Something like: 就像是: my.namespace.ColorEnum = { RED : 0,......

技术盛宴
25分钟前
14
0
linux 手动挂载硬盘没有移到回收站解决方法

linux 手动挂载硬盘没有移到回收站解决方法 修改挂载硬盘的文件夹权限为当前用户即可

小熊宝宝
29分钟前
24
0
spring集成kafka

1、引入依赖jar包 <dependency><groupId>org.springframework.kafka</groupId><artifactId>spring-kafka</artifactId></dependency> 2、配置kafka信息 spring: kafka: bootstra......

简到珍
33分钟前
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部