P1659

发表于 分类于
[国家集训队]拉拉队排练

[国家集训队]拉拉队排练

雨荨发现，如果连续的一段女生，有$ \huge{奇数}$ 个，并且他们手中的牌子所写的字母，从左到右和从右到左读起来一样，那么这一段女生就被称作和谐小群体。

论读题的重要性。。。。

Manacher 再做个前缀和就完了。

时间复杂度 $O(n)$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}
using Ehnaev::read;using Ehnaev::write;

const ll mo=19930726,N=1e6;

ll n,k,m,ans;
ll d[N+5],c1[N+5];
char s[N+5],a[N+5];

inline ll pow(ll b,ll p) {
  ll res=1;while(p) {if(p&1) res=(res*b)%mo;b=(b*b)%mo;p>>=1;}return res;
}

int main() {

  n=read();k=read();
  scanf("%s",a);

  s[0]='#';for(ll i=0;i<n;i++) {s[i*2+1]=a[i];s[i*2+2]='#';}
  m=n*2+1;

  for(ll l=0,r=-1,i=0;i<m;i++) {
    ll k=(i>r)?0:min(d[l+r-i],r-i+1);
    while(i-k>=0&&i+k<m&&s[i-k]==s[i+k]) k++;
    d[i]=k--;if(i+k>r) {r=i+k;l=i-k;}
  }

  for(ll i=0;i<m;i++) {
    if(s[i]!='#') c1[(d[i]-1)/2]++;
    // printf("s[%lld]=%c d[%lld]=%lld\n",i,s[i],i,d[i]);
  }

  ll ans=1;
  for(ll i=n/2;i>=0;i--) {
    c1[i]=c1[i+1]+c1[i];
    if(k>=c1[i]) {ans=(ans*pow(i*2+1,c1[i]))%mo;k-=c1[i];}
    else {ans=(ans*pow(i*2+1,k))%mo;k=0;break;}
    // printf("ans=%lld\n",ans);
  }

  // printf("k=%lld\n",k);
  if(k>0) write(-1);
  else write(ans);

  return 0;
}