Submission #64856282

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#define MOD_BY 6165748424457383623ULL
#define MULT 556365909070653953ULL
typedef unsigned long long ull;
ull add(ull a, ull b) {
  return a + b - MOD_BY * (a + b >= MOD_BY);
}
ull sub(ull a, ull b) {
  return b == 0 ? a : add(a, MOD_BY - b);
}
ull mul(ull a, ull b) {
  ull r = 0;
  while (b > 0) {
    if (b & 1) r = add(r, a);
    a = add(a, a);
    b >>= 1;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>

#define MOD_BY 6165748424457383623ULL
#define MULT 556365909070653953ULL

typedef unsigned long long ull;

ull add(ull a, ull b) {
	return a + b - MOD_BY * (a + b >= MOD_BY);
}

ull sub(ull a, ull b) {
	return b == 0 ? a : add(a, MOD_BY - b);
}

ull mul(ull a, ull b) {
	ull r = 0;
	while (b > 0) {
		if (b & 1) r = add(r, a);
		a = add(a, a);
		b >>= 1;
	}
	return r;
}

ull pou(ull a, ull b) {
	ull r = 1;
	while (b > 0) {
		if (b & 1) r = mul(r, a);
		a = mul(a, a);
		b >>= 1;
	}
	return r;
}

ull inv(ull a) {
	return pou(a, MOD_BY - 2);
}

char S[512345];

ull from_left[512345], from_left_sum[512345];
ull from_right[512345], from_right_sum[512345];

ull mult_pow[512345], inv_mult_pow[512345];

int main(void) {
	int len, i;
	if (scanf("%512344s", S) != 1) return 1;
	mult_pow[0] = 1;
	mult_pow[1] = MULT;
	inv_mult_pow[0] = 1;
	inv_mult_pow[1] = inv(MULT);
	for (i = 0; S[i] != '\0'; i++) {
		if (i > 1) {
			mult_pow[i] = mul(mult_pow[i - 1], MULT);
			inv_mult_pow[i] = mul(inv_mult_pow[i - 1], inv_mult_pow[1]);
		}
		from_left[i] = mul(S[i], mult_pow[i]);
		if (i > 0) {
			from_left_sum[i] = add(from_left_sum[i - 1], from_left[i]);
		} else {
			from_left_sum[i] = from_left[i];
		}
	}
	len = i;
	for (i = len - 1; i >= 0; i--) {
		from_right[i] = mul(S[i], mult_pow[len - 1 - i]);
		from_right_sum[i] = add(from_right_sum[i + 1], from_right[i]);
	}
	for (i = len; i > 0; i--) {
		ull lhash = mul(sub(from_left_sum[len - 1], i < len ? from_left_sum[len - 1 - i] : 0), inv_mult_pow[len - i]);
		if (lhash == from_right_sum[len - i]) {
			/* 右の部分が回文 → あとは残り (左) をひっくり返してくっつければおｋ */
			int j;
			fputs(S, stdout);
			for (j = len - i - 1; j >= 0; j--) {
				putchar(S[j]);
			}
			putchar('\n');
			return 0;
		}
	}
	puts("ERROR!!!!!");
	return 0;
}

Submission Info

Judge Result