【洛谷 P1659】 [国家集训队]拉拉队排练(manacher)

时间:2021-08-22 18:39:00

题目链接

马拉车+简单膜你

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 11000010;
const int MOD = 19930726;
char b[MAXN], a[MAXN << 1];
int hw[MAXN << 1], ans = 1, n, c[MAXN];
#define ll long long
ll now, m;
int fast_pow(int a, ll k){
int ans = 1;
while(k){
if(k & 1) ans = (ll)ans * a % MOD;
a = (ll) a * a % MOD;
k >>= 1;
}
return ans;
}
int main(){
scanf("%d%lld", &n, &m);
scanf("%s", b);
a[0] = a[1] = '#';
for(int i = 0; i < n; ++i)
a[(i << 1) + 2] = b[i], a[(i << 1) + 3] = '#';
int maxright = 0, mid; n = (n << 1) + 3;
for(int i = 1; i < n; ++i){
if(i < maxright)
hw[i] = min(hw[(mid << 1) - i], hw[mid] + mid - i);
else hw[i] = 1;
while(a[i + hw[i]] == a[i - hw[i]]) ++hw[i];
if(hw[i] + i > maxright){
maxright = hw[i] + i;
mid = i;
}
++c[hw[i] - 1];
}
for(int i = (n - 3) >> 1; i; --i){
if(i & 1 ^ 1) continue;
now += c[i];
if(m <= now){ ans = (ll) ans * fast_pow(i, m) % MOD; m = 0; break; }
m -= now; ans = (ll) ans * fast_pow(i, now) % MOD;
}
if(m) ans = -1;
printf("%d\n", ans);
return 0;
}