CodeForces 305E Playing with String (SG函数)

Let's consider substring of s s[i… j], that all characters from i to j are palindrome centers, and i - 1, j + 1 are not. Every such substring can be treated independently from the others, and as we don't need to know it'sstructure let's consider only it length len. Let's calculategrundy[len] — Grundy function. If we want to cut character at position i 0 ≤ i < len then our game splits in to independent ones: first will have length i - 1, second — len - i - 2, as s[i - 1] and s[i + 1] are not centers of palindrome any more.

#include <cstdio>
#include <memory.h>
#include <cstring>

inline int max(int a, int b) { if (a >= b) return a; return b; }

const int N = 5005;
char s[N];
int grundy[N], mex[N], n, totalXor;

int main(){
	gets(s);
	for(int i = 1; i < N; i++) {
		memset(mex, 0, sizeof mex);
		for(int j = 0; j < i; j++) {
			int left = max(0, j - 1);
			int right = max(0, i - j - 2);
			int tXor = grundy[left] ^ grundy[right];
			if (tXor < N) mex[tXor]++;
		}
		for(int j = 0; ; j++) {
			if (!mex[j]) {
				grundy[i] = j;
				break;
			}
		}
	}
	n = strlen(s);
	for(int i = 1; i < n - 1; i++) {
		if (s[i-1] == s[i + 1]) {
			int j = i;
			while (j + 2 < n && s[j] == s[j + 2]) j++;
			totalXor ^= grundy[j - i + 1];
			i = j + 1;
		}
	}
	if (totalXor != 0) {
		puts("First");
		for(int i = 1; i < n - 1; i++) {
			if (s[i-1] == s[i+1]) {
				int j = i;
				while (j + 2 < n && s[j] == s[j + 2]) j++;
				int len = j - i + 1;
				int nowXor = totalXor ^ grundy[len];
				for(int k = 0; k < len; k++) {
					int left = max(0, k - 1);
					int right = max(0, len - k - 2);
					int resXor = nowXor ^ grundy[left] ^ grundy[right];
					if (resXor == 0) {
						printf("%dn", i + k + 1);
						return 0;
					}
				}
				i = j + 1;
			}
		}
	}
	puts("Second");
}