bzoj1030: [JSOI2007]文本生成器(AC自动机+DP)
2024-08-27 05:38:17
第一次写这类题...懵
直接计算答案不好计算,所以补集转化求不合法的方案。
首先考虑朴素的DP,设$f(i, s)$表示前$i$个字符,字符串为$s$的方案数,且任意一个给定串都不存在$s$中。
我们知道在一个字符串里找其他的字符串是AC自动机的强项,那么我们就可以考虑在AC自动机上跑DP,每次$+j$都在AC自动机上匹配,如果匹配到单词结尾的话就不能转移,否则就是可以转移的。
所以设$f(i, j)$为前$i$个字符,当前匹配到AC自动机上第$j$个节点的方案数,如果沿着fail一直往上的所有节点都不是单词结尾就可以转移了。
注意是大写字母T_T
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define MOD(x) ((x)>=mod?(x)-mod:(x))
#define ll long long
using namespace std;
const int maxn=, maxm=, mod=;
struct poi{int nxt[], fail;}tree[maxn*maxm];
int n, m, ans, tott;
int f[maxm][maxn], h[maxn];
bool cnt[maxn];
char s[maxm];
inline void read(int &k)
{
int f=; k=; char c=getchar();
while(c<'' || c>'') c=='-'&&(f=-), c=getchar();
while(c<='' && c>='') k=k*+c-'', c=getchar();
k*=f;
}
inline void insert()
{
int len=strlen(s+), now=;
for(int i=, ch;i<=len;i++)
{
if(!tree[now].nxt[ch=s[i]-'A'])
tree[now].nxt[ch]=++tott;
now=tree[now].nxt[ch];
}
cnt[now]=;
}
inline void getfail()
{
int front=, rear=; tree[].fail=-;
for(int i=, too;i<;i++)
if((too=tree[].nxt[i])) h[++rear]=too;
while(front<=rear)
{
int now=h[front++];
for(int i=, too;i<;i++)
if((too=tree[now].nxt[i]))
tree[too].fail=tree[tree[now].fail].nxt[i], h[++rear]=too;
else tree[now].nxt[i]=tree[tree[now].fail].nxt[i];
cnt[now]|=cnt[tree[now].fail];
}
}
int main()
{
read(n); read(m);
for(int i=;i<=n;i++) scanf("%s", s+), insert();
getfail(); f[][]=;
for(int i=;i<=m;i++)
for(int j=;j<=tott;j++)
if(!cnt[j]) for(int k=;k<;k++)
f[i][tree[j].nxt[k]]=MOD(f[i][tree[j].nxt[k]]+f[i-][j]);
for(int i=;i<=tott;i++) if(!cnt[i]) ans=MOD(ans+f[m][i]);
int tot=; for(int i=;i<=m;i++) tot=1ll*tot*%mod;
printf("%d\n", MOD(tot-ans+mod));
}
最新文章
- 如何学习Oracle
- libc++
- poj1753枚举
- thinkphp中的分表方法
- ACM1877_又一版A+B
- C# 计算器 如果设置键盘输入的监听事件
- poj1066 Jugs
- 敏感字符串加密处理(PHP实现)
- MySQL从库忽略某些错误
- java web:在eclipse中如何创建java web 项目
- class的二般用法
- Hbase多列范围查找(效率)
- C语言gets雨scanf函数的用法
- SQL窗口函数RANK(),Dense_Rank(),row_number(),NTILE()
- 20164319 刘蕴哲 Exp5 MSF基础应用
- WinCHM 制作开发知识库,So easy!!!
- P3605 [USACO17JAN]Promotion Counting晋升者计数
- 浅谈Java Future接口
- [.net 多线程]线程基础
- 爬虫必备—scrapy-redis(分布式爬虫)
热门文章
- Kafka下的生产消费者模式与订阅发布模式
- 2017-2018-2 20155224 『网络对抗技术』Exp9:Web安全基础
- mount状态下表空间情报试验
- MiZ702学习笔记11——如何使用vivado isim仿真
- 记一次Spring的aop代理Mybatis的DAO所遇到的问题
- .Net Core WebApi控制器接收原始请求正文内容
- onSaveInstanceState和onRestoreInstanceState触发的时机
- java批量爬取电影资源
- Shell 基础 -- 流编辑器 sed 详解
- EOS开发基础之五:使用cleos命令行客户端操作EOS——智能合约之Exchange