Nodepad numpy pdf jqgrid jaxb grid tags Momentjs 百度seo关键词 vue网页 vue钩子函数 pmp视频 ssr链接解析 python随机数 python在线教程 python使用正则表达式 java环境 javadate java对象 java编程实例 java数据结构 java函数 java有哪些数据类型 java求阶乘 java安装教程 java输出 linuxtar命令 python 教程 bcdautofix vbs脚本 subprocess linux命令详解词典 内存整理工具 51脚本 js绝对值 考试练习系统 高通cpu排行 bz2 linux运维之道 掌门一对一下载
当前位置: 首页 > 学习教程  > 编程语言

【题解】 [CF17E] Palisection

2020/12/28 19:19:35 文章标签:

solution: 很容易想到用回文自动机做。manacher算法也可以,但是我们这里不考虑。 但是这道题直接做并不好做。我的第一个思路是分两种情况讨论: 左端点或右端点重合,那么枚举一个左右端点即可包含或者交叉,枚举第一个回文子串[l…

solution:
很容易想到用回文自动机做。manacher算法也可以,但是我们这里不考虑。

但是这道题直接做并不好做。我的第一个思路是分两种情况讨论:

  • 左端点或右端点重合,那么枚举一个左右端点即可
  • 包含或者交叉,枚举第一个回文子串 [ l , r ] [l,r] [l,r],然后计算区间 [ l 2 , r 2 ] [l2,r2] [l2,r2]的数量,其中 l 2 < r < r 2 l2<r<r2 l2<r<r2

这个做法是不会算重的。然而有两个瓶颈:一是这个枚举就是 O ( n 2 ) O(n^2) O(n2)的了,计算交叉的区间数虽然可以用前缀和预处理,但是预处理也是 O ( n 2 ) O(n^2) O(n2)的。而 n = 2 ∗ 1 0 6 n=2*10^6 n=2106,显然必须严格 O ( n ) O(n) O(n)

正难则反。我们考虑计算不相交的回文子串的数量,再用总方案减去即可。而计算不相交只需正反各跑一次自动机即可。注意第二次跑时不需要清零。所以 O ( n ) O(n) O(n)即可解决。

但是我们知道回文自动机的空间复杂度是 O ( n ∗ 26 ) O(n*26) O(n26),本题会暴空间,所以应该用邻接表储存。相当于用时间换空间。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
//相交点:p
//[l,r]包含p
//求[l,r]的数量?
//应该可做,不过要用数据结构的来维护(甚至树上数据结构) 
//常数太大,舍弃 
const int N=2e6+5;
const int mod=51123987;
struct node{
	int len,fail,cnt;
}prt[N];
int n,num,len,lst; 
int head[N],nxt[N],to[N],col[N],_cnt;
long long res,ans,sum[N],sum2[N];
char s[N];
void add(int x,int y,int z) {
	to[++_cnt]=y,col[_cnt]=z,nxt[_cnt]=head[x],head[x]=_cnt;
}
int get(int x,int y) {
	for(int i=head[x];i!=-1;i=nxt[i])
	    if(col[i]==y) return to[i];
	return 0;
}
int getfail(int x) {
	while(s[n-prt[x].len-1]!=s[n]) x=prt[x].fail;
	return x;
}
void extand(int x) {
	int cur=getfail(lst);
	int now=get(cur,x);
	if(!now) {
		now=++num;
		prt[now].len=prt[cur].len+2;
		prt[now].fail=get(getfail(prt[cur].fail),x);
		add(cur,now,x);
		prt[now].cnt=prt[prt[now].fail].cnt+1;
	} 
	lst=now;
	
}
int main() {
	memset(head,-1,sizeof(head));
	num=lst=1,prt[1].len=-1,prt[0].fail=prt[1].fail=1,prt;
	scanf("%d",&len); scanf("%s",s+1);
	for(n=1;n<=len;n++) extand(s[n]-'a'),sum[n]=prt[lst].cnt%mod;
    reverse(s+1,s+1+len);
    lst=1;
	for(n=1;n<=len;n++) {
		extand(s[n]-'a'),sum2[n]=(sum2[n-1]+prt[lst].cnt)%mod;
	}
	for(int i=1;i<len;i++) {
		ans+=(long long)sum[i]*sum2[len-i]%mod;
		ans%=mod;
	}
	res=(long long)sum2[len]*(sum2[len]-1)/2%mod;
	res-=ans;
	res=(res+mod)%mod;
	printf("%lld",res);
}

本文链接: http://www.dtmao.cc/news_show_550202.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?