Основное
 
 
Отправитель Задача Язык Вердикт Время Память Отослано Протест.  
120193424 Дорешивание:
yy_makemelove
932G - 30 GNU C++11 Полное решение 78 мс 131124 КБ 2021-06-21 12:30:21 2021-06-21 12:30:21
→ Исходный код
#include <bits/stdc++.h>
using namespace std;
int read() {
	char c = getchar();
	int x = 0;
	while(c < '0' || c > '9')	c = getchar();
	while(c >= '0' && c <= '9')	x = x * 10 + c - 48,c = getchar();
	return x;
}
const int _ = 1e6 + 7;
char s[_],t[_];
int g[_],dp[_] ;
int n;
#define mod 1000000007
void add(int &x,int y) {
	x += y - mod;
	x += (x >> 31) & mod;
}
namespace PAM {
	int now,ch[_][27],dif[_],slink[_],fail[_],len[_];
	int cnt = 0;
	int getfail(int p,int pos) {
		while(t[pos-len[p]-1] != t[pos])	p = fail[p];
		return p;
	}
	void ins(int pos) {
		now = getfail(now,pos);
		int c = t[pos] - 'a';
		if(!ch[now][c]) {
			int x = ++cnt;
			len[x] = len[now] + 2;
			fail[x] = ch[getfail(fail[now],pos)][c];
			ch[now][c] = x;now = x;
			dif[x] = len[x] - len[fail[x]];
			if (dif[x] == dif[fail[x]])	slink[x] = slink[fail[x]];
			else	slink[x] = fail[x];
		}
		else	now = ch[now][c];
	}
	void build() {
		fail[0] = 1,len[0] = 0;
		len[1] = -1;now = ++cnt;
		scanf("%s",s+1);
		n = strlen(s+1);
		if (n & 1){
			puts("0");
			exit(0);
		}
		dp[0] = 1;
		for (int i = 1,j = 0; i <= n / 2; ++i)	t[++j] = s[i],t[++j] = s[n-i+1];
		t[n+1] = '\0';
		for (int i = 1; i <= n; ++i) {
			ins(i);
			for (int x = now; x > 1; x = slink[x]) {
				g[x] = dp[i-dif[x]-len[slink[x]]];
				if (dif[x] == dif[fail[x]])	add(g[x],g[fail[x]]);
				if (i % 2 == 0)	add(dp[i],g[x]);
			}
		}
//		for (int i = 2; i <= cnt; ++i)	cout << i <<' ' << fail[i] <<' '<<len[i] <<'\n';
		cout << dp[n] << '\n';
	}
}
int main() {
	PAM::build();
	return 0;
}
?
Время: ? ms, память: ? КБ
Вердикт: ?
Ввод
?
Вывод участника
?
Ответ жюри
?
Комментарий чекера
?
Диагностика
?
Показать детали тестирования