?
№ | Отправитель | Задача | Язык | Вердикт | Время | Память | Отослано | Протест. | |
---|---|---|---|---|---|---|---|---|---|
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; }
?
?
?
?