BZOJ1030:[JSOI2007]文本生成器

2021-06-22 00:04

阅读：677

标签：pen scanf clu pac sub 更新 insert nbsp can

1030: [JSOI2007]文本生成器

Time Limit: 1 Sec Memory Limit: 162 MB
Submit: 4859 Solved: 2019
[Submit][Status][Discuss]

Description

　　JSOI交给队员ZGX一个任务，编制一个称之为“文本生成器”的电脑软件：该软件的使用者是一些战舰狗，
他们现在使用的是GW文本生成器v6版。该软件可以随机生成一些文章―――总是生成一篇长度固定且完全随机的文
章—— 也就是说，生成的文章中每个字节都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词，
那么我们说这篇文章是可读的（我们称文章a包含单词b，当且仅当单词b是文章a的子串）。但是，即使按照这样的
标准，使用者现在使用的GW文本生成器v6版所生成的文章也是几乎完全不可读的?。ZGX需要指出GW文本生成器 v6
生成的所有文本中可读文本的数量，以便能够成功获得v7更新版。你能帮助他吗？

Input

　　输入文件的第一行包含两个正整数，分别是使用者了解的单词总数N (定长度M；以下N行，每一行包含一个使用者了解的单词。这里所有单词及文本的长度不会超过100，并且只可能包
含英文大写字母A..Z

Output

　　一个整数，表示可能的文章总数。只需要知道结果模10007的值。

Sample Input

2 2
A
B

Sample Output

100

思路{

　　AC自动机裸题。

　　然而对于我这种一道AC自动机都没刷过的

　　只会匹配的辣鸡来说还是比较难的。

　　肯定想到是DP，怎么设状态！

　　我们应当明确求神马。直接求方案数不行。

　　那也可以总情况数减去不行的方案数。

　　我们想，一个目标串行的话最多走到AC自动机末尾的点前一个为止，或者fail链的点前一个。

　　而目标串只走m步！就DP啦～～～～

　　dp[i][k]表示匹配 i 步到 k 点的方案数

　　那转移方程:dp[i][ch[k][j]]+=dp[i-1][k];

　　就可以啦～～～～～～～～～～～

}

#include
#define RG register
#define il inline
#define N 60010
using namespace std;

int ch[N][27],f[N],cc,n,k;
char s[N*2];
bool in[N];

void Insert(){
  int now=0,len=strlen(s+1);int h=1;
  while(hque;
  while(!que.empty())que.pop();que.push(0);
  while(!que.empty()){
    RG int u=que.front();
    for(RG int i=0;i>1));
  tmp=(tmp*tmp)%MOD;if(b&1)tmp=(tmp*a)%MOD;
  return tmp;
}
int dp[101][N];

int main(){
  freopen("1.in","r",stdin);
  freopen("1.out","w",stdout);
  scanf("%d%d",&n,&k);
  for(int i=1;i=MOD)dp[i][ch[j][K]]-=MOD;
	}
      }int ans=qpow(26,k);
  for(int i=0;i

BZOJ1030:[JSOI2007]文本生成器

标签：pen scanf clu pac sub 更新 insert nbsp can

原文地址：http://www.cnblogs.com/zzmmm/p/7172419.html

上一篇：利用CSS简单布局的不同组合类型

下一篇：nodejs实如今线群聊

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：BZOJ1030:[JSOI2007]文本生成器
文章链接：http://soscw.com/index.php/essay/97127.html

亲，登录后才可以留言！

BZOJ1030:[JSOI2007]文本生成器

1030: [JSOI2007]文本生成器

Description

Input

Output

Sample Input

Sample Output

评论

热门文章

推荐文章

最新文章

置顶文章