<[Sdoi2014]数数>,<Sdoi14R1D1T2 Problem Count> - JoishBadeR - Holy Sh*t
<[Sdoi2014]数数>,<Sdoi14R1D1T2 Problem Count>
Description
给定一个长度不超过1200的整数N，问从1~N的范围里有多少个整数的子串不包括S集合里的任何串。
|S|<=50,S集合中的所有串的长度和在1500范围内。样例：Input: 20 3 2 3 14 Output: 14 解释：1~20中不包含{2,3,14}的显然有{1,4,5,6,7,8,9,10,11,15,16,17,18,19}这么多
Solution:
裸Ac自动机Dp。
直接在Ac自动机上统计就行了。。。
建完Ac自动机后，从低位向高位枚举，num表示当前位的数
0 .. i .. Len-1
假设我们枚举到了i
1.如果0~i-1的数都能放下，那么0~i-1位就以N的0~i-1位开头，第i位是0~num-1的这些东西都是合法的，加入答案（如果是最高位需要去掉前导0）
2.如果不是最高位的话，那么0~i-1位全是0，第i位是0~9这些东西也都是合法的，加入答案
因为条件1的制约条件，我们枚举Len-1位时，显然没有把N这个数算到答案里。所以如果N能放下，答案+1，dp结束
关于自动机的写法大概是一个人一个写法吧。。自认为这种写法比较省时省力
从Root结点广搜，每次用队首元素x->fail->node[i] 更新 (x->node[i] ? x->node[i]->fail : x->node[i])
#include<cstdio>
#include<cstring>
using namespace std;
namespace AcDp
{
const int MAXN = 1510, P = 1000000007;
struct Tac
{
Tac *num[10], *fail; bool flag; int sum, w;
} ePool[MAXN], *Pool = ePool, *root, *q[MAXN];
int N, M, tot, ans; char s[MAXN], str[MAXN];
inline void renew(int &x, int y) { x += y; x %= P; }
void Solve()
{
scanf("%s%d", str, &M); N = strlen(str);
(root = Pool++)->fail = root;
for(int i = 1; i <= M; ++i)
{
scanf("%s", s); Tac *temp = root;
for(int j = 0; s[j]; ++j)
{
int now = s[j] - 48;
if(!temp->num[now])
temp->num[now] = Pool++;
temp = temp->num[now];
}
temp->flag = 1;
}
int h = 0, t = 0;
for(int i = 0; i < 10; ++i)
if(root->num[i])
{
q[++t] = root->num[i];
root->num[i]->fail = root;
}
else root->num[i] = root;
while(h < t)
{
Tac *x = q[++h];
for(int i = 0; i < 10; ++i) if(x->num[i])
{
x->num[i]->fail = x->fail->num[i];
x->num[i]->flag|= x->fail->num[i]->flag;
q[++t] = x->num[i];
}
else x->num[i] = x->fail->num[i];
}
for(int i = 0; &ePool[i] != Pool-1; ++i)
if(ePool[i].flag == 0) ePool[i].sum = 1;
for(int i = N; i; --i)
{
Tac *temp = root;
int num = str[i-1] - 48; bool flag = 1;
for(int j = 0; j < i - 1; ++j)
{
temp = temp->num[str[j] - 48];
if(temp->flag) { flag = 0; break; }
}
if(flag) for(int j = (i == 1); j < num; ++j) renew(ans, temp->num[j]->sum);
if(i != 1) for(int j = 1; j < 10; ++j) renew(ans, root->num[j]->sum);
for(int j = 0; &ePool[j] != Pool-1; ++j)
{
Tac *now = &ePool[j]; now->w = 0;
if(now->flag) continue;
for(int k = 0; k < 10; ++k)
renew(now->w, now->num[k]->sum);
}
for(int j = 0; &ePool[j] != Pool-1; ++j) ePool[j].sum = ePool[j].w;
}
bool flag = 1; Tac *temp = root;
for(int i = 0; i < N; ++i)
{
temp = temp->num[str[i] - 48];
if(temp->flag) { flag = 0; break; }
}
printf("%d\n", (ans + flag) % P);
}
}
int main()
{
freopen("count.in", "r", stdin);
freopen("count.out", "w", stdout);
AcDp::Solve();
return 0;
}
Hint：
这大概是一轮中最一眼的题了吧。。但是比较恶心= =、进队爷肯定随便切了吧。。像我这种在考场上代码能力比较神奇的蒟蒻只能瞪着眼看了。。。
评论 (0)