Tang-Dreamoon's Blog

bzoj 2160 拉拉队排练

发表于 | 分类于 ， ，

字符串的世界连接着眷恋和希冀

　　题目链接：bzoj 2160

　　题意：写 B z o j 的题意就是简单——题意见上……

　　题解：马拉车的模板题，问题是如何求出所有的回文串。显然如果一个回文串的长度是X那么X-2，X-4，X-6……都是回文串，网上许多人的方法是差分求前缀和，即在1的位置＋1，在X+2的位置减一，然后X位置的前缀和就是X的出现次数，然后加一个快速幂就可以求解了。不过我没有用网上的做法，我选择把以每个位置为中心的回文串长度降序排序。长度为X的回文串在数组中最后出现的位置就是它出现的次数。一个意思……

　　我思故我在：一开始我智障到 K 没有用 L L 存导致 W A 了几遍。╮(╯▽╰)╭唉！

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
char ap[1001000];
int len[1001000];
long long  modd=19930726;
bool cmp(int a,int b)
{
	return a > b ;
}
long long kmi(long long a,long long b)
{
	long long now=a%modd,ret=1;
	while(b)
	{
		if(b&1) ret=ret*now%modd;
		now=now*now%modd;
		b>>=1;
	}
	return ret;
}
int main()
{
	int n;
	long long k;
	scanf("%d%lld",&n,&k);
	scanf("%s",ap+1);
	len[1]=0;
	int now=1;
	for(int i=2;i<=n;i++)
	{
		if(i<=now+len[now])
		{
			int x=now-(i-now);
			if(x-len[x]>now-len[now]) len[i]=len[x];
			else
			{
				int j=now+len[now]-i+1;
				while((j+i)<=n&&(i-j)>=1&&ap[i+j]==ap[i-j]) j++;
				now=i,len[i]=j-1;
			}
		}
		else
		{
			int j=1;
			while((j+i)<=n&&(i-j)>=1&&ap[i+j]==ap[i-j]) j++;
			now=i,len[i]=j-1;
		}
	}
	for(int i=1;i<=n;i++)
		len[i]=len[i]*2+1;
	long long ans=1;
	long long love=0;
	long long sum=0;
	sort(len+1,len+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		sum+=(len[i]+1)/2;
	}
	if(sum<k)
	{
		puts("-1");
		return 0;
	}
	len[n+1]=0;
	for(int i=1;i<=n;i++)
	{
		while(len[i]>len[i+1])
		{
			if(love+i<=k)
			{
				ans=ans*kmi(len[i],i)%modd;
			}
			else
			{
				ans=ans*kmi(len[i],k-love)%modd;
				love=k;break;
			}
			love+=i,len[i]-=2;
		}
		if(love==k) break;
	}
	cout<<ans<<endl;
	return 0;
}