这道题好像只要跑一个Manacher就能过……
要求的女生和谐小群体就是求一个回文串，然后同时要计算这个回文串的子串。这个很简单，我们跑一遍Manacher算出每个点的最长回文半径，然后长度为偶数的忽略（题目要求），奇数的计算一下前缀和，然后对于每一个长度用快速幂计算一下同时k减去回文串个数就行，直到k=0。
注意此题要开longlong而且别把模数打错了……
看一下代码。
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<set> #include<vector> #include<queue> #define pb push_back #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar(' ') using namespace std; typedef long long ll; const int M = 40005; const int N = 1000005; const ll mod = 19930726; ll read() { ll ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { ans *= 10; ans += ch - '0'; ch = getchar(); } return ans * op; } ll qpow(ll a,ll b) { ll q = 1; while(b) { if(b&1) q *= a,q %= mod; a *= a,a %= mod; b >>= 1; } return q; } int p[N<<1],mx,mid,len; char s[N<<1],c[N]; ll n,k,sum[N],ans = 1; int change() { int j = 2,l = strlen(c); s[0] = '!',s[1] = '#'; rep(i,0,l-1) s[j++] = c[i],s[j++] = '#'; s[j] = '@'; return j; } void manacher() { len = change(),mx = mid = 1; rep(i,1,len-1) { if(i < mx) p[i] = min(mx-i,p[(mid<<1)-i]); else p[i] = 1; while(s[i-p[i]] == s[i+p[i]]) p[i]++; if(mx < i + p[i]) mid = i,mx = i + p[i]; sum[p[i]-1]++; } } int main() { n = read(),k = read(); scanf("%s",c); manacher(); //rep(i,1,n) printf("%d ",p[i]);enter; //per(i,n,1) printf("%lld ",sum[i]);enter; per(i,n,1) { if(!(i&1)) continue; sum[i] += sum[i+2]; //printf("%d %lld %lld ",i,k,sum[i]); if(k >= sum[i]) ans *= qpow(i,sum[i]),ans %= mod,k -= sum[i]; else { ans *= qpow(i,k),ans %= mod; k = 0; break; } } if(k) printf("-1 "); else printf("%lld ",ans); return 0; }