【洛谷 P1659】 [國家集訓隊]拉拉隊排練（manacher）

題目鏈接
馬拉車+簡單膜你

#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;
}