| 题目名称 | 1468. [SPOJ 1676]文本生成器 |
|---|---|
| 输入输出 | textgen.in/out |
| 难度等级 | ★★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2013-12-30加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：57， 提交：202， 通过率：28.22% | ||||
 cstdio |
100 | 0.020 s | 0.31 MiB | C++ |
 Hzoi_Hugh |
100 | 0.028 s | 0.32 MiB | C++ |
 _Horizon |
100 | 0.035 s | 0.39 MiB | C++ |
 lm-stl |
100 | 0.036 s | 0.28 MiB | C++ |
|
Hzoi_Hugh |
100 | 0.037 s | 0.32 MiB | C++ |
 stdafx.h |
100 | 0.038 s | 0.31 MiB | C++ |
 liu_runda |
100 | 0.042 s | 0.39 MiB | C++ |
 op_组撒头屯 |
100 | 0.046 s | 1.40 MiB | C++ |
 fye |
100 | 0.051 s | 0.38 MiB | C++ |
 Milky Way |
100 | 0.051 s | 0.39 MiB | C++ |
| 本题关联比赛 | |||
| 201712练习 | |||
| 2022级数学专题练习赛4 | |||
| 关于 文本生成器 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
噢这题和JSOI那道题数据范围不一样。单词数少了但是文章长了
 Rapiz
2017-03-12 11:15
7楼
| ||||
|
%%%
| ||||
|
回复 @Chenyao2333 :
AC自动机+矩阵加速可以做到O((12n)^3*logL) | ||||
|
思路漂移的跟王者小弟的灵车一样。。。。
| ||||
|
@cstdio 如果用AC自动机复杂度可以做到O(NM)之下嘛?我O(NM)的T成狗........
| ||||
|
被这道题卡了好久。。。Y_Y忘记考虑状态会重复了。。。。
 C语言入门
2014-01-07 19:36
2楼
| ||||
|
俞华程，《矩阵乘法在信息学中的应用》，国家集训队2008论文集
这道题可以不用AC自动机（好吧我就没用）……也可以用…… | ||||
yourfather
FoolMike
mikumikumi
Chenyao2333【题目描述】
给定 $N(1\le N\le 10)$ 个长度不超过 $6$ 的大写单词，求由大写字母组成，长度为 $L(1\le L\le 10^6)$ 的，包含至少一个给定单词的字符串有多少个，答案 $\bmod \ 10007$。
【输入格式】
输入的第一行有两个整数：$N,L$，表示单词个数和字符串长度。
接下来的 $N$ 行，每行有一个由大写字母组成的单词。
【输出格式】
一个整数 $ans$，表示包含至少一个给定单词的字符串个数模 $10007$ 的值。
【样例输入1】
2 2 A B
【样例输出1】
100
【样例输入2】
2 10000 ABC B
【样例输出2】
5960
【提示】
对于 $60\%$ 的数据，$1\le N\le 6$，$1\le L\le 10^5$。
对于 $100\%$ 的数据，$1\le N\le 10$，$1\le L\le 10^6$。