P1659 [國家集訓隊]拉拉隊排練

題目描述

艾利斯頓商學院籃球隊要參加一年一度的市籃球比賽了。拉拉隊是籃球比賽的一個看點，好的拉拉隊往往能幫助球隊增加士氣，赢得最終的比賽。是以作為拉拉隊隊長的楚雨荨同學知道，幫助籃球隊訓練好拉拉隊有多麼的重要。

拉拉隊的選拔工作已經結束，在雨荨和校長的挑選下，n位集優秀的身材、舞技于一體的美女從衆多報名的女生中脫穎而出。這些女生将随着籃球隊的小夥子們一起，和對手抗衡，為艾利斯頓籃球隊加油助威。

一個陽光明媚的早晨，雨荨帶領拉拉隊的隊員們開始了排練。n個女生從左到右排成一行，每個人手中都舉了一個寫有26個小寫字母中的某一個的牌子，在比賽的時候揮舞，為小夥子們呐喊、加油。

雨荨發現，如果連續的一段女生，有奇數個，并且他們手中的牌子所寫的字母，從左到右和從右到左讀起來一樣，那麼這一段女生就被稱作和諧小群體。

現在雨荨想找出所有和諧小群體，并且按照女生的個數降序排序之後，前K個和諧小群體的女生個數的乘積是多少。由于答案可能很大，雨荨隻要你告訴她，答案除以19930726的餘數是多少就行了。

輸入輸出格式

輸入格式：

輸入為标準輸入。

第一行為兩個正整數n和K，代表的東西在題目描述中已經叙述。

接下來一行為n個字元，代表從左到右女生拿的牌子上寫的字母。

輸出格式：

輸出為标準輸出。

輸出一個整數，代表題目描述中所寫的乘積除以19930726的餘數，如果總的和諧小群體個數小于K，輸出一個整數-1。

輸入輸出樣例

輸入樣例#1： 

5 3
ababa      

輸出樣例#1： 

45
      

說明

樣例說明

和諧小群體女生所拿牌子上寫的字母從左到右按照女生個數降序排序後為ababa, aba, aba, bab, a, a, a, b, b，前三個長度的乘積為 。

資料範圍與約定

測試點	n	K
1	10
2-3	100
4-7	1,000
8	100,000	= 1
9-11
12-14		1,000,000,000,000
15-17	500,000
18	1,000,000
19
20

Solution：

　　既然剛學了“馬拉車”，于是打道題練手，發現洛谷除了模闆就這一道manacher的題了，看來馬拉車果然很冷門啊！

　　閑話少說，說下思路。

　　本題我們發現其實就是給定一個長度為n的字元串和一個k，求前k個長度為奇數的回文子串的長度乘積，不足k個就輸出-1。

　　算法就是manacher+快速幂，因為隻需要長度為奇數的回文子串，于是不需要構造新串，在求每個中心的最長回文子串半徑時，将出現過的半徑值都用一個桶來統計，因為長度最長為n（≤1,000,000），是以不會有問題。輸出時，從離n最近的奇數枚舉到1出現的奇數，由于k很大而且相同的數可能有很多重複，于是對于每個桶中的數直接快速幂求乘積，然後相應的将k減小，知道已經累乘過的數的個數大于等于k就跳出循環。輸出時判斷一下就ok了。

#include<bits/stdc++.h>
#define il inline
#define ll long long
#define debug printf("%d %s\n",__LINE__,__FUNCTION__)
using namespace std;
const int N=1000050,mod=19930726;
ll p[N],sum,tot[N];
ll n,k,ans=1;
char s[N];
il ll fast(ll x,ll k)
{
    ll ans=1;
    while(k){
        if(k&1)ans=ans*x%mod;
        k>>=1;
        x=x*x%mod;
    }
    return ans;
}
il void manacher()
{
    int id,mx=-1;
    for(ll i=1;i<=n;i++){
        if(i<mx)p[i]=min(p[2*id-i],mx-i);
        else p[i]=1;
        while(s[i+p[i]]==s[i-p[i]])p[i]++;
        if(mx<i+p[i])mx=i+p[i],id=i;
        tot[2*p[i]-1]++;
    }
}
int main()
{
    scanf("%lld%lld%s",&n,&k,s+1);
    s[0]='$';
    manacher();
    //for(int i=1;i<=n;i++)cout<<tot[i];
    for(int i=n%2==0?n-1:n;i>=1;i-=2){
        sum+=tot[i];
        if(sum>k){ans=ans*fast(i,k)%mod;break;}
        else {ans=ans*fast(i,sum)%mod;k-=sum;}
    }
    if(sum<k){cout<<-1;return 0;}
    cout<<ans;
    return 0;
}