洛谷-P4052 文本生成器
虽然这题应该称为记忆化搜索,但是就想当做数位DP(QAQ)
一开始数组开小了,导致了WA,TLE,RE以及两个AC,深深的体会到了数组开小了什么错误都有,哈哈
题意:给出一个字典,求长度为M且包含字典中至少一个单词的文本有多少个。
思路:
-
虽然是要求可读文本的数量,但是毕竟要构造多字符串的匹配还是比较麻烦的,因此可以转化为求 总文本数-不可读文本数
-
转化后总文本数可以直接快速幂搞定,不可读文本数可以在AC自动机上跑数位DP,别跑那些认识的单词就行啦!
题目描述
JSOI交给队员ZYX一个任务,编制一个称之为“文本生成器”的电脑软件:该软件的使用者是一些低幼人群,他们现在使用的是GW文本生成器v6版。
该软件可以随机生成一些文章―――总是生成一篇长度固定且完全随机的文章—— 也就是说,生成的文章中每个字节都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词,那么我们说这篇文章是可读的(我们称文章a包含单词b,当且仅当单词b是文章a的子串)。但是,即使按照这样的标准,使用者现在使用的GW文本生成器v6版所生成的文章也是几乎完全不可读的?。ZYX需要指出GW文本生成器 v6
生成的所有文本中可读文本的数量,以便能够成功获得v7更新版。你能帮助吗?
输入格式
输入文件的第一行包含两个正整数,分别是使用者了解的单词总数N (<= 60),GW文本生成器 v6生成的文本固定长度M;以下N行,每一行包含一个使用者了解的单词。这里所有单词及文本的长度不会超过100,并且只可能包含英文大写字母A…Z
输出格式
一个整数,表示可能的文章总数。只需要知道结果模10007的值。
输入输出样例
输入
2 2
A
B
输出
100
//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}
const int maxn = 2e4+10;
const int mod = 1e4+7;
const double eps = 1e-9;
int N, M;
char s[110];
int trie[maxn][26], fail[maxn], ed[maxn], cnt;
int dp[110][maxn];
int fast(int a, int k) {
if(!k) return 1;
int now=fast(a,k/2);
now=now*now%mod;
if(k&1) now=now*a%mod;
return now;
}
void insert() {
int len=strlen(s), p=0;
for(int i=0; i<len; ++i) {
int k=s[i]-'A';
if(!trie[p][k]) trie[p][k]=++cnt;
p=trie[p][k];
}
ed[p]=1;
}
void build() {
queue<int> q;
for(int i=0; i<26; ++i) if(trie[0][i]) q.push(trie[0][i]);
while(q.size()) {
int now=q.front(); q.pop();
for(int i=0; i<26; ++i) {
if(trie[now][i]) {
fail[trie[now][i]]=trie[fail[now]][i];
if(ed[trie[fail[now]][i]]) ed[trie[now][i]]=1;
q.push(trie[now][i]);
}
else trie[now][i]=trie[fail[now]][i];
}
}
}
int dfs(int pos, int now) {
if(pos>M) return 1;
if(~dp[pos][now]) return dp[pos][now];
int ans=0;
for(int i=0; i<26; ++i)
if(!ed[trie[now][i]]) ans+=dfs(pos+1,trie[now][i]);
return dp[pos][now]=ans%mod;
}
int main() {
//ios::sync_with_stdio(false);
N=read(), M=read();
for(int i=0; i<N; ++i) scanf("%s", s), insert();
build();
memset(dp,-1,sizeof(dp));
printf("%d\n", (fast(26,M)-dfs(1,0)+mod)%mod);
}
洛谷 P-3311 数数
这题跟上面那题几乎一样,不过这是真正的数位DP,2333
题意:给出一个字典,求不大于N的且包含字典中任意字符串的正整数有多少个。
思路:
- 当然是建好AC自动机
- 然后在上面跑数位DP呀,别踩坑点就行
- 比如前缀0不能跑
题目描述
我们称一个正整数N是幸运数,当且仅当它的十进制表示中不包含数字串集合S中任意一个元素作为其子串。例如当S=(22,333,0233)时,233是幸运数,2333、20233、3223不是幸运数。 给定N和S,计算不大于N的幸运数个数。
输入格式
输入的第一行包含整数N。 接下来一行一个整数M,表示S中元素的数量。 接下来M行,每行一个数字串,表示S中的一个元素。
输出格式
输出一行一个整数,表示答案模109+7的值。
输入输出样例
输入
20
3
2
3
14
输出
14
//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}
const int maxn = 1e4+10;
const int mod = 1e9+7;
const double eps = 1e-9;
char s[maxn];
int trie[maxn][10], fail[maxn], cnt, ed[maxn];
ll ans;
void insert() {
int len=strlen(s), p=0;
for(int i=0; i<len; ++i) {
int k=s[i]-'0';
if(!trie[p][k]) trie[p][k]=++cnt;
p=trie[p][k];
}
ed[p]=1;
}
void build() {
queue<int> q;
for(int i=0; i<10; ++i) if(trie[0][i]) q.push(trie[0][i]);
while(q.size()) {
int now=q.front(); q.pop();
for(int i=0; i<10; ++i) {
if(trie[now][i]) {
fail[trie[now][i]]=trie[fail[now]][i];
if(ed[trie[fail[now]][i]]) ed[trie[now][i]]=1;
q.push(trie[now][i]);
}
else trie[now][i]=trie[fail[now]][i];
}
}
}
int dp[1210][1510];
int N, tot, num[1210];
void getnum() {
tot=strlen(s);
for(int i=0; i<tot; ++i) num[i]=s[i]-'0';
}
int dfs(int pos, int now, int first, int f) {
if(pos==tot) return !first;
if(!first&&!f&&~dp[pos][now]) return dp[pos][now];
ll ans=0;
int up=f?num[pos]:9;
for(int i=0; i<=up; ++i) {
if(i) {
if(!ed[trie[now][i]]) ans+=dfs(pos+1,trie[now][i],0,i==up&&f);
}
else if(!first) {
if(!ed[trie[now][i]]) ans+=dfs(pos+1,trie[now][i],0,i==up&&f);
}
else ans+=dfs(pos+1,now,1,i==up&&f);
}
ans%=mod;
if(!first&&!f) dp[pos][now]=(int)ans;
return (int)ans;
}
int main() {
//ios::sync_with_stdio(false);
memset(dp,-1,sizeof(dp));
scanf("%s", s);
getnum();
int M=read();
for(int i=0; i<M; ++i) scanf("%s", s), insert();
build();
printf("%d\n", dfs(0,0,1,1));
}