hihocoder 后缀自动机四·重复旋律7
2024-08-23 20:22:50
在\(DAG\)上跑一个\(dp\)就好了
设\(ans_i\)表示到了\(SAM\)的\(i\)位置上所有的子串形成的数的和,之后我们顺便记录一个方案数\(d_i\)
之后我们直接转移就好了
\[ans_v+=ans_u\times 10+w[u,v]\times d_u
\]
\]
\[d_v+=d_u
\]
\]
答案是\(\sum_{i=1}^{cnt} ans_i\)
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 1000005
#define re register
#define LL long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const LL mod=1e9+7;
int n,m,cnt=1,lst=1;
char S[maxn];
int fa[maxn<<1],len[maxn<<1],son[maxn<<1][11];
LL ans[maxn<<1],d[maxn<<1];
int q[maxn<<1],top,r[maxn<<1];
inline void ins(int c)
{
int f=lst,p=++cnt; lst=p;
len[p]=len[f]+1;
while(f&&!son[f][c]) son[f][c]=p,f=fa[f];
if(!f) {fa[p]=1;return;}
int x=son[f][c];
if(len[f]+1==len[x]) {fa[p]=x;return;}
int y=++cnt;
len[y]=len[f]+1,fa[y]=fa[x],fa[x]=fa[p]=y;
for(re int i=0;i<=10;i++) son[y][i]=son[x][i];
while(f&&son[f][c]==x) son[f][c]=y,f=fa[f];
}
int main()
{
scanf("%d",&m);
for(re int i=1;i<=m;i++)
{
scanf("%s",S+1);n=strlen(S+1);
for(re int j=1;j<=n;j++) ins(S[j]-'0');
ins(10);
}
for(re int i=1;i<=cnt;i++)
for(re int j=0;j<=10;j++) r[son[i][j]]++;
q[++top]=1,d[1]=1;
for(re int i=1;i<=top;i++)
{
for(re int j=0;j<10;j++)
{
if(!son[q[i]][j]) continue;
r[son[q[i]][j]]--;
d[son[q[i]][j]]=(d[q[i]]+d[son[q[i]][j]])%mod;
ans[son[q[i]][j]]=(ans[son[q[i]][j]]+d[q[i]]*(LL)j%mod+10ll*ans[q[i]]%mod)%mod;
if(!r[son[q[i]][j]]) q[++top]=son[q[i]][j];
}
if(!son[q[i]][10]) continue;
r[son[q[i]][10]]--;
if(!r[son[q[i]][10]]) q[++top]=son[q[i]][10];
}
LL now=0;
for(re int i=2;i<=cnt;i++) now=(now+ans[i])%mod;
printf("%lld\n",now);
return 0;
}
最新文章
- 【Android】Vitamio 4.0 正式版发布/ Vitamio IOS 测试版发布(2013-07-16)
- ios证书
- 【转】预编译头文件来自编译器的早期版本,或者预编译头为 C++ 而在 C 中使用它(或相反)
- linux 读取input输入设备demo
- 【JS】Beginner9:Arrays
- c语言学习之基础知识点介绍(二十):预处理指令
- 移植opencv库到zedboard(制作运行库镜像) 分类: OpenCV ZedBoard ubuntu shell Eye_Detection 2014-11-08 18:48 172人阅读 评论(0) 收藏
- java之package与import
- QT中QWidget类简介
- jQuery克隆DOM节点
- ISO文件:AMD64和i386的区别
- Java中的集合概述
- mysql的学习笔记(二)
- Apache为mysql以及自己的项目设置虚拟路径
- SpringMVC没有接受到参数的坑
- wifi,Android渗透之arp欺骗
- DBMS_RANDOM 用法
- BZOJ5137[Usaco2017 Dec]Standing Out from the Herd
- 汉诺塔python实现
- Thrift笔记(一)--Hello Demo
热门文章
- Rsa2加密报错java.security.spec.InvalidKeySpecException的解决办法
- pandas to_excel、to_csv的float_format参数设置
- (转)Cobbler无人值守批量安装Linux系统
- Oracle 基础系列之1.2 oracle的基本使用
- 阿里云服务器对外开放tomcat端口访问
- 简介SWT Jface
- Radix tree--reference
- Java Mail邮件发送的简单实现
- js控制5秒返回指定界面,或上一个界面
- java输出九九乘法口诀表