题目传送门: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; }
好文章!666,学习了
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!
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!
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!
If you are going for best contents like myself, only visit this web site everyday because it provides quality
contents, thanks
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.
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!
This is a topic that is close to my heart… Many thanks!
Exactly where are your contact details though?
What’s up to every one, as I am genuinely keen of reading this web site’s post to be updated regularly.
It carries nice information.
Hi there to every single one, it’s in fact
a good for me to go to see this web page, it includes precious Information.
Wow, this paragraph is fastidious, my sister is analyzing
these things, thus I am going to tell her.
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.
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
I appreciate, result in I discovered exactly what I was looking for.
You’ve ended my four day long hunt! God Bless you man.
Have a great day. Bye
Hurrah, that’s what I was exploring for, what a data!
existing here at this web site, thanks admin of this website.
This blog was… how do I say it? Relevant!! Finally I’ve found something which helped me.
Kudos!
Hi there to all, how is all, I think every one is getting more from this site, and your views are fastidious designed for
new users.
I every time emailed this website post page to all my associates, as
if like to read it afterward my friends will too.
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!
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.
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
This article is actually a good one it assists new the web users,
who are wishing in favor of blogging.
Wow! In the end I got a website from where I know how
to actually take valuable data concerning my study and knowledge.
What’s up, I want to subscribe for this webpage to take most up-to-date
updates, so where can i do it please assist.
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!
You got a very excellent website, Gladiola I discovered it through yahoo.