rt

$80$分,#2\3\7\21 WA

这是魔法吗QAQ

#include <bits/stdc++.h>
#define int long long int

using namespace std;

const int N = 1e6 + 70,MOD = 19930726;

int len = 0;
int p[N << 1],num[N];
char s[N << 1];

inline int min(int a,int b){return a < b ? a : b;}

inline int read(){
    int x = 0,f = 1;
	char ch = getchar();
	for(;!isdigit(ch);ch = getchar())
		if(ch == '-') f = -1;
	for(;isdigit(ch);ch = getchar())
		x = (x << 1) + (x << 3) + ch -'0';
	return x * f;
}

int ksm(int a,int c){
    if(a == 1) return 1;
    int tmp  = 1;
    while(c){
        if(c & 1) tmp = (tmp * a) % MOD;
        c >>= 1;
        a = (a * a) % MOD;
    }
    return tmp;
}

signed main()
{
    int n = read(),k = read();
    s[len] = '`';
    s[++ len] = '#';
    for(int i = 1; i <= n;i ++){
        s[++ len] = getchar();
        s[++ len] = '#';
    }
    s [++ len] = '$';

    int id = 0,r = 0;

    for(int i = 1;i <= len;i ++){

        p[i] = (r > i) ? (min(p[id * 2 - i],r - i)) : 1;

        while(s[i + p[i]] == s[i - p[i]]) p[i] ++;

        if(p[i] + i > r){r = i + p[i];id = i;}
        
		if((p[i] - 1) % 2)num[p[i] - 1] ++;

    }

    int sum = 0,res = 1;
    for(int i = n;i;i --){
        if(i & 1){
            sum += num[i];
            if(sum >= k){
                res = (res * ksm(i,k)) % MOD;
                k -= sum;
                break;
            }
            else{
                res = (res * ksm(i,sum)) % MOD;
                k -= sum;
            }
        }
    }
    res %= MOD;
    if(k > 0) res = -1;
    cout << res;
    return 0;
}