比赛 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;
}