马拉车+简单膜你
#include #include #include 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 longll 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;}