Manacher【p1659】 [国家集训队]拉拉队排练

题目描述

n个女生举牌子(只含有26个小写字母,长度为n的字符串), 如果连续的一段女生，有奇数个，并且她们手中的牌子所写的字母，从左到右和从右到左读起来一样，那么这一段女生就被称作和谐小群体。

现在想找出所有和谐小群体，并且按照女生的个数降序排序之后，前K个和谐小群体的女生个数的乘积是多少。由于答案可能很大，输出除以19930726的余数。

分析

显然,一个和谐小群体是一个长度为奇数的回文串。

理所当然地我们想到了manacher算法

manacher算法可以求出每个位置的回文半径.

所以我们可以用manacher来解决此题

然后因为这个题只需要求出奇数长度的回文串

所以不需要考虑插入字符(其实也可以插入

由于最后一个点十分大 k<10^12(辣么长

所以需要快速幂加速一下

掉坑现场

重点个人认为

求出了某一位置的回文半径

就像样例解释中一样

  eg：a b a b a

  回文半径为5

  但它也包含了 a bab ababa！

即如果一个值为x(x>1)那x-1,x-2.....也存在

所以我们需要前缀和来做

(感觉不应该叫前缀和啊emm 但又感觉差不多)

我们可以用桶存储一下回文半径,倒着搜一遍即可

(:з」∠) (胳膊没了

----------------代码------------------

一代码部分参考bolg @five20

#include<bits/stdc++.h>

#define IL inline

#define RI register long long

#define N 1000008

#define mod 19930726

char s[N<<1],ch[N];

long long n,k,len,RL[N<<1],mxxnum,sum,ans=1;

long long MaxRight,center,tong[N<<1];

IL long long ksm(long long x,long long y)

{

	long long res=1;

	for(;y;y>>=1,x=x*x%mod)

		if(y&1)res=res*x%mod;

	return res;

}

int main()

{

	scanf("%lld%lld",&n,&k);

	scanf("%s",s+1);

	for(RI i=1;i<=n;i++)

	{

		if(i<=MaxRight)RL[i]=std::min(MaxRight-i,RL[2*center-i]);

		else RL[i]=1;

		while(i+RL[i]<=n&&i-RL[i]>=0&&s[i+RL[i]]==s[i-RL[i]])++RL[i];

		if(i+RL[i]-1>MaxRight)MaxRight=i+RL[i]-1,center=i;

		tong[2*RL[i]-1]++;

	}

	//for(RI i=1;i<=n;i++)printf("%lld ",tong[i]);

	if(n%2!=1)n--;

	for(RI i=n;i>=1;i-=2)

	{

		sum+=tong[i];

		if(sum>k)

		{

			ans=ans*ksm(i,k)%mod;

			break;

		}

		else

		{

			ans=ans*ksm(i,sum)%mod;

			k-=sum;

		}

	}

	if(sum<k)printf("-1");

	else printf("%lld\n",ans);

}

好了好了我知道丑了emmmm

巴特西

Manacher【p1659】 [国家集训队]拉拉队排练

一代码部分参考bolg @five20

最新文章

热门文章