比赛 |
20201031 |
评测结果 |
WWWWWWTTTTTTTTTTTTTT |
题目名称 |
贪吃的毛毛 |
最终得分 |
0 |
用户昵称 |
锝镆氪锂铽 |
运行时间 |
14.001 s |
代码语言 |
C++ |
内存使用 |
18.20 MiB |
提交时间 |
2020-10-31 20:58:12 |
显示代码纯文本
#include <iostream>
#include <cstring>
#include <cstdio>
#define uLL unsigned long long
#define LL long long
using namespace std;
const int maxN = 1e6;
const int p = 99991;
int Minrp(char *s, int l);
int mull(int a, int b);
int hhash(char *a);
bool KMP(int *a, int *b);
bool insert(char *a);
void print(int *a);
uLL a, b;
int tot, ans = 0;
char c[20];
char snow[maxN][20] = {}, head[maxN] = {}, nxt[maxN];
int main(void) {
freopen("greed.in", "r", stdin);
freopen("greed.out", "w", stdout);
scanf("%llu%llu", &a, &b);
sprintf(c, "%llu", b);
if (!insert(c))
ans ++;
for (; a <= b; a ++) {
sprintf(c, "%llu", a);
if (!insert(c)) {
ans ++;
}
}
printf("%d\n", ans);
return 0;
}
int mull(int a, int b) {
LL ans = 0;
for (; b; b >>= 1) {
if (b & 1)
ans = (ans + a) % p;
a = a * 2 % p;
}
return (int)ans % p;
}
int hhash(char *a) {
int sum = 0, mul = 1;
for (int i = 0; i < strlen(a); i ++) {
sum += (a[i] - '0');
sum %= p;
mul = mull(mul, (int)(a[i] - '0'));
}
return (sum + mul) % p;
}
bool KMP(char *a, char *b) {
int len = strlen(a);
char c[len * 2];
memcpy(c, a, sizeof(char) * len);
memcpy(c + len, a, sizeof(char) * len);
int ne[len + 2];
int i = 0, j = -1;
ne[0] = -1;
while (i < len) {
if (j == -1 || b[i] == b[j]) {
ne[++i] = ++j;
}
else
j = ne[j];
}
int lenc = len * 2;
int lenb = strlen(b);
i = 0, j = 0;
while (i < lenc && j < lenb) {
if (j == -1 || c[i] == b[j]) {
j++;
i++;
}
else
j = ne[j];
}
if (j == lenb)
return true;
else
return false;
}
bool insert(char *a) {
int val = hhash(a);
int len = strlen(a);
for (int i = head[val]; i; i = nxt[i]) {
if (KMP(snow[i], a))
return true;
for (int j = 0; j < (len / 2); j ++) {
swap(a[j], a[len - 1 - j]);
}
if (KMP(snow[i], a))
return true;
}
tot ++;
memcpy(snow[tot], a, sizeof(int) * len);
nxt[tot] = head[val];
head[val] = tot;
return false;
}