【Tsinsen 1393】Palisection

题目传送门:http://www.tsinsen.com/A1393
离线版题目:http://paste.ubuntu.com/17953857/
数据生成器:http://paste.ubuntu.com/17953893/

这一道题目想了很久很久。没有想出来。想统计的量,对于每一个位置是变动的,貌似没有什么数据结构可以维护
于是可耻地看了题解 >︿<
好吧,是在下输了。统计相交的情况比较麻烦,但可以统计不相交的 QAQ
另外提个醒:本题可能会求的回文串的数量,这货最多是O(n)的,有些地方不要忘了开long long或及时取模

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = 2000000+9;
const LL MOD = 51123987;

char pat[MAXN];
int n;

namespace Palindromic_Tree{
	#define PAM Palindromic_Tree
	#define SIGMA_SIZE 26
	int ch[MAXN][SIGMA_SIZE],sz[MAXN];
	int fail[MAXN],len[MAXN],cnt,last;
	int num[MAXN],rnum[MAXN],ti[MAXN]; 
	LL Sum;
	
	inline int newnode(){
		int ret = ++cnt;
		memset(ch[ret],0,sizeof(ch[ret]));
		len[ret] = fail[ret] = sz[ret] = ti[ret] = 0;
		return ret;
	}
	
	inline void extend(int p, int c){
		int w = last;
		while (pat[p-len[w]-1] != pat[p]) w = fail[w];
		if (!ch[w]){
			int nw = newnode(), k = fail[w];
			while (pat[p-len[k]-1] != pat[p]) k = fail[k];
			len[nw] = len[w]+2; fail[nw] = ch[k]; ch[w] = nw;
			ti[nw] = ti[fail[nw]] + 1; 
		}
		last = ch[w];
		sz[last]++;
	}
	
	inline void build(){
		last = cnt = 1;
		fail[0] = fail[1] = 1;
		len[1] = -1; len[0] = 0;
		for (int i=1;i<=n;i++)
			extend(i,pat[i]-'a'),
			num[i] = ti[last];
		
		last = 1; cnt = -1;
		newnode(); newnode();
		fail[0] = fail[1] = 1;
		len[1] = -1; len[0] = 0;
		for (int i=1;i<=n/2;i++) swap(pat[i],pat[n-i+1]);
		for (int i=1;i<=n;i++) extend(i,pat[i]-'a'), rnum[n-i+1] = (ti[last]+rnum[n-i+2]) % MOD; for (int i=cnt;i>1;i--)
			sz[fail[i]] = (sz[fail[i]]+sz[i]) % MOD,
			Sum = (Sum+sz[i])%MOD;
	}
	
	inline int solve(){
		LL ret = 0;
		for (int i=1;i<n;i++)
			ret = (ret+(LL)num[i]*(LL)rnum[i+1]) % MOD; 
		ret = (Sum*(Sum-1)/2LL)%MOD - ret;
		return int((ret%MOD+MOD)%MOD);
	}
};

int main(){
	scanf("%d%s",&n,pat+1);
	PAM::build();
	printf("%d\n",PAM::solve());
	return 0;
}

26 thoughts to “【Tsinsen 1393】Palisection”

  1. Right here is the right blog for everyone who wants to find out about this
    topic. You know so much its almost tough to argue with you
    (not that I really would want to…HaHa). You certainly put
    a brand new spin on a topic which has been written about for decades.
    Wonderful stuff, just wonderful!

  2. Woah! I’m really loving the template/theme of this website.

    It’s simple, yet effective. A lot of times it’s hard to get that
    “perfect balance” between superb usability and visual
    appearance. I must say that you’ve done a superb job with this.
    In addition, the blog loads very fast for me
    on Opera. Excellent Blog!

  3. Heya great blog! Does running a blog such as this take a great deal of work?
    I have no understanding of computer programming however I was
    hoping to start my own blog soon. Anyhow,
    should you have any suggestions or techniques for new blog owners please share.
    I know this is off subject however I just had to ask. Thanks a lot!

  4. Howdy, i read your blog from time to time and i own a similar
    one and i was just curious if you get a lot of spam feedback?

    If so how do you stop it, any plugin or anything you can suggest?
    I get so much lately it’s driving me crazy so any assistance is
    very much appreciated.

  5. That is a great tip particularly to those new to the blogosphere.
    Short but very precise info… Thank you for sharing this one.

    A must read article!

  6. I’ve been surfing online more than 3 hours today, yet I never
    found any interesting article like yours.
    It’s pretty worth enough for me. In my view, if all webmasters and bloggers made
    good content as you did, the internet will be a lot more useful than ever
    before.

  7. I just could not go away your web site before suggesting that I actually loved the usual info an individual supply in your visitors? Is gonna be back ceaselessly in order to inspect new posts

  8. Amazing blog! Do you have any recommendations for aspiring
    writers? I’m planning to start my own site soon but I’m a little lost on everything.
    Would you advise starting with a free platform like WordPress or go
    for a paid option? There are so many choices out there that
    I’m totally overwhelmed .. Any recommendations? Thanks a lot!

  9. I love what you guys are usually up too. This kind of clever work and coverage!
    Keep up the fantastic works guys I’ve included you guys to my blogroll.

  10. I love your blog.. very nice colors & theme.
    Did you design this website yourself or did you hire someone
    to do it for you? Plz answer back as I’m looking to
    design my own blog and would like to know where u got this from.
    thanks a lot

  11. Hi there! I could have sworn I’ve visited
    this website before but after going through some of the articles I realized it’s new to me.
    Regardless, I’m certainly happy I found it and I’ll be bookmarking it and checking back often!

发表评论

电子邮件地址不会被公开。 必填项已用*标注