【BZOJ 3103】[ONTAK2010] Palindromic Equivalence

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3103
神犇题解:http://foreseeable97.logdown.com/posts/194507-herbicidalontak2010palindromic-equivalence

解题报告

这些字符串相关的计数题已经做过很多了吧?
这题显然就是给定$O(n)$个相等与不等的关系,让你求染色方案数
这样直接做好像是一个$NP$的问题?就是四色定理那个一般化后的问题

但这题有一个非常好的性质,如果我们把一个等价类看成点,不等关系看成边
那么每一个联通块都是一个完全图!也就是一个弦图!
弦图的染色方案数是可以使用完美消除序列在$O(n)$的时间复杂度内解决的
有因为这题是完全图,所以任意一个$1 \sim n$的排列都是完美消除序列
于是直接从$1 \to n$进行计算即可

至于这图是个弦图图的证明,想一想还是很简单的(虽然不怎么容易观察出来)
我们可以参考:http://foreseeable97.logdown.com/posts/194507-herbicidalontak2010palindromic-equivalence

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2000009;
const int M = N << 1;
const int MOD = 1000000007;

char pat[N],s[N];
int n,ans=1,fa[N],rid[N],col[N];
int vis[N],head[N],nxt[M],to[M]; 
vector<pair<int,int> > e;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int find(int x) {
	return x == fa[x]? x: fa[x] = find(fa[x]);
}

inline void manacher() {
	for (int i=1,r=1,p=1,t;i<=n*2;i++) {
		t = min(r - i, rid[p - (i - p)]);
		while (s[i+t+1] == s[i-t-1]) t++, fa[find(i+t)] = find(fa[i-t]);
		if ((rid[i] = t) + i > r) r = t + i, p = i;
		e.push_back(make_pair(i - t - 1, i + t + 1));
	}
}

inline void AddEdge(int u, int v) {
	static int E = 1; 
	if (u == v || !(u & 1) || !(v & 1)) return;
	to[++E] = v; nxt[E] = head[u]; head[u] = E;
	to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

int main() {
	scanf("%s",pat+1); n = strlen(pat+1); 
	s[0] = '#'; s[n*2] = '@';
	for (int i=1;i<=n;i++) s[i*2-1] = pat[i], s[i*2] = '*';
	for (int i=1;i<=n*2;i++) fa[i] = i;
	manacher();
	for (int i=0;i<e.size();i++) AddEdge(find(e[i].first), find(e[i].second));
	for (int i=1,cnt;cnt=26,i<=n*2;i+=2) {
		if (find(i) != i) continue; col[i] = 1;
		for (int j=head[i];j;j=nxt[j]) {
			if (col[to[j]] && vis[to[j]] < i) 
				--cnt, vis[to[j]] = i;
		}  
		if (cnt <= 0) ans = 0; 
		else ans = (LL)ans * cnt % MOD;
	}
	cout<<ans;
	return 0;
}

—————————— UPD 2017.4.26 ——————————
今天我们机房讨论了一下,这货是个弦图,不一定是一个完全图

242 thoughts to “【BZOJ 3103】[ONTAK2010] Palindromic Equivalence”

  1. I have been exploring for a bit for any high quality articles or blog
    posts in this sort of area . Exploring in Yahoo I eventually stumbled upon this site.

    Reading this info So i’m glad to exhibit that I have
    a very good uncanny feeling I came upon exactly what I needed.
    I most unquestionably will make sure to do not overlook this web site
    and give it a glance on a constant basis.

  2. You really make it appear so easy together with your presentation but
    I to find this topic to be really one thing which I believe
    I’d by no means understand. It sort of feels too complicated and very
    large for me. I’m looking ahead in your next publish, I will try to get the hang of it!

  3. Hi! Quick question that’s entirely off topic.
    Do you know how to make your site mobile friendly?
    My blog looks weird when browsing from my iphone 4.
    I’m trying to find a template or plugin that might
    be able to correct this problem. If you have any recommendations, please share.
    Thanks!

  4. Heya i’m for the primary time here. I found this board and I find It really useful & it helped me out a
    lot. I am hoping to provide one thing back and aid others such as you helped me.

  5. I’m really loving the theme/design of your site. Do you
    ever run into any web browser compatibility issues? A small number of
    my blog visitors have complained about my blog
    not operating correctly in Explorer but looks great in Safari.
    Do you have any solutions to help fix this problem?

  6. Thank you, I have recently been looking for information approximately this topic for a long time and yours is the greatest I’ve came upon till now.
    But, what concerning the conclusion? Are you positive in regards to the source?

  7. Hi I am so happy I found your web site, I really found
    you by mistake, while I was browsing on Google for something else,
    Nonetheless I am here now and would just like to say many thanks for a marvelous
    post and a all round exciting blog (I also love the theme/design), I don’t have time to look
    over it all at the minute but I have saved it and also added in your RSS feeds,
    so when I have time I will be back to read a lot
    more, Please do keep up the superb jo.

  8. Hello there I am so grateful I found your web site,
    I really found you by error, while I was browsing
    on Yahoo for something else, Nonetheless I am here now
    and would just like to say kudos for a fantastic post and a all round entertaining blog (I also love the theme/design), I don’t have time to look over it all at the minute but I have bookmarked it and also added in your RSS
    feeds, so when I have time I will be back to read a lot more, Please
    do keep up the great work.

  9. I’m not sure where you are getting your info, but
    great topic. I needs to spend some time learning much more or understanding more.
    Thanks for wonderful info I was looking for this info for my mission. natalielise pof

  10. I do not know if it’s just me or if everybody else experiencing
    problems with your website. It seems like some of the written text on your posts are running off the screen. Can someone else please comment and let me know if this is happening to them
    too? This might be a issue with my internet browser because I’ve had
    this happen before. Cheers

  11. I do not even understand how I stopped up here, however I assumed this submit was once
    good. I do not understand who you’re however certainly you’re going to a famous blogger when you are not already.
    Cheers!

  12. Everything is very open with a really clear description of the challenges.
    It was really informative. Your website is useful. Many thanks for sharing!

  13. Hi! I know this is kinda off topic however I’d figured I’d ask.
    Would you be interested in exchanging links or maybe guest writing
    a blog post or vice-versa? My website goes over a lot of the same topics as yours and I believe we could greatly benefit
    from each other. If you are interested feel free to send me
    an e-mail. I look forward to hearing from you!
    Awesome blog by the way! natalielise plenty of fish

  14. I think what you typed made a bunch of sense.
    But, consider this, what if you added a little content?

    I mean, I don’t want to tell you how to run your website, but suppose you added something that makes
    people want more? I mean 【BZOJ 3103】[ONTAK2010] Palindromic Equivalence – Qizy's Database is a little plain. You ought to peek at Yahoo’s
    home page and watch how they write article headlines to get people to click.
    You might try adding a video or a pic or two to get readers excited
    about what you’ve got to say. Just my opinion, it would make
    your posts a little bit more interesting.

  15. With havin so much content and articles do you ever run into
    any problems of plagorism or copyright infringement?

    My blog has a lot of unique content I’ve either authored
    myself or outsourced but it looks like a lot of it is
    popping it up all over the web without my agreement. Do you know any ways
    to help prevent content from being ripped off?
    I’d really appreciate it.

  16. Nice post. I learn something new and challenging on blogs I stumbleupon everyday.
    It’s always interesting to read content from other authors and practice something from their websites.

  17. Wonderful beat ! I wish to apprentice even as you amend your website, how can i subscribe for a weblog web site?

    The account helped me a appropriate deal. I have been tiny bit acquainted of
    this your broadcast offered vibrant transparent
    idea

  18. This design is incredible! You certainly know how to keep a reader entertained.
    Between your wit and your videos, I was almost moved to start my own blog (well, almost…HaHa!)
    Great job. I really loved what you had to say, and more than that, how you
    presented it. Too cool!

  19. Greetings I am so glad I found your website, I really found you by error,
    while I was browsing on Digg for something else, Anyhow I am here now and
    would just like to say cheers for a tremendous post and a all round entertaining blog (I also love the theme/design), I don’t have time
    to look over it all at the minute but I have saved
    it and also added your RSS feeds, so when I have time I will be back
    to read much more, Please do keep up the great work.

  20. Hello this is kinda of off topic but I was wondering if blogs use WYSIWYG editors or if you have to
    manually code with HTML. I’m starting a blog soon but have no coding experience so
    I wanted to get guidance from someone with experience.

    Any help would be greatly appreciated!

  21. I am extremely impressed with your writing skills as
    well as with the layout on your blog. Is this a paid theme or did you modify
    it yourself? Either way keep up the nice quality writing, it’s rare to see a nice blog like this
    one nowadays.

  22. It is appropriate time to make a few plans for the long run and
    it is time to be happy. I have learn this submit and if I may just I want to
    recommend you few attention-grabbing things or tips. Perhaps you can write subsequent articles regarding this article.

    I want to learn more things approximately it!

  23. Greetings! Quick question that’s totally off topic. Do
    you know how to make your site mobile friendly?
    My weblog looks weird when browsing from my iphone.
    I’m trying to find a template or plugin that might be able to fix this problem.
    If you have any suggestions, please share. Appreciate it!

  24. I truly love your website.. Great colors & theme.
    Did you develop this amazing site yourself? Please reply back as I’m trying
    to create my very own website and want to know where you got this from or what
    the theme is called. Appreciate it!

  25. I loved as much as you will receive carried out right
    here. The sketch is attractive, your authored subject matter stylish.
    nonetheless, you command get bought an nervousness over that you wish be delivering the following.
    unwell unquestionably come more formerly again since exactly the same nearly a lot
    often inside case you shield this hike.

  26. Good day! This is kind of off topic but I
    need some guidance from an established blog. Is it hard to set up your own blog?
    I’m not very techincal but I can figure things out pretty quick.

    I’m thinking about creating my own but I’m not sure where to begin. Do you have any points or suggestions?

    Many thanks

  27. Hi would you mind letting me know which webhost you’re using?
    I’ve loaded your blog in 3 completely different internet browsers and I must
    say this blog loads a lot faster then most. Can you suggest a good internet hosting provider at a fair price?
    Thanks, I appreciate it!

  28. With havin so much content and articles do you ever run into any issues of plagorism
    or copyright infringement? My website has a lot of unique content I’ve either created myself or outsourced but it appears a lot of it is popping it up all over the
    internet without my authorization. Do you
    know any methods to help reduce content from being ripped
    off? I’d really appreciate it.

  29. I loved as much as you’ll receive carried out right here.
    The sketch is attractive, your authored subject matter stylish.
    nonetheless, you command get bought an impatience over that you wish be delivering the following.
    unwell unquestionably come more formerly again since exactly the
    same nearly a lot often inside case you shield this increase.

  30. I’m extremely impressed with your writing skills as well as with the layout on your weblog.
    Is this a paid theme or did you modify it yourself? Either way keep up the excellent quality writing, it’s rare to
    see a nice blog like this one nowadays.

  31. Definitely consider that that you stated. Your favourite justification appeared to be on the
    net the easiest thing to take into accout of.
    I say to you, I definitely get irked at the same time as other people think about
    worries that they just do not recognise about.
    You managed to hit the nail upon the top as smartly as
    outlined out the whole thing with no need side-effects ,
    other people could take a signal. Will probably be again to get more.
    Thanks

  32. I truly love your website.. Excellent colors & theme. Did you develop this website yourself?
    Please reply back as I’m planning to create my own personal website and
    want to find out where you got this from or just what the theme
    is called. Kudos!

  33. This is really interesting, You are a very skilled blogger.
    I’ve joined your feed and look forward to seeking more of your great
    post. Also, I have shared your website in my social networks!

  34. Excellent items from you, man. I’ve take into accout your stuff previous to and you’re simply extremely
    excellent. I really like what you have obtained here, certainly
    like what you’re stating and the best way wherein you say it.

    You make it entertaining and you still take care of to keep
    it sensible. I cant wait to read far more from
    you. This is actually a great website.

  35. Fantastic beat ! I wish to apprentice at the same time as you amend your web site, how can i subscribe for a weblog web site?
    The account aided me a acceptable deal. I were tiny bit
    acquainted of this your broadcast provided vibrant clear concept

  36. Do you have a spam issue on this website; I also am a blogger, and I was wondering your situation; we have created some nice practices and we are looking to trade solutions with others, be sure to shoot me an e-mail if interested.

  37. I was recommended this blog by means of my cousin. I’m no longer positive whether or not this
    submit is written by way of him as nobody else recognize such specific approximately
    my trouble. You’re amazing! Thank you!

  38. Asking questions are genuinely pleasant thing if you are not understanding something
    fully, but this paragraph offers good understanding yet.

  39. Fantastic beat ! I wish to apprentice while you amend your site, how can i subscribe for a blog
    website? The account aided me a acceptable deal. I had been a little bit acquainted of this your broadcast offered bright clear concept

  40. Oh my goodness! Impressive article dude! Thanks, However I am going through troubles with your RSS.
    I don’t understand why I am unable to join it. Is there anybody having identical RSS problems?

    Anyone who knows the solution can you kindly respond? Thanks!!

  41. Thank you for the good writeup. It actually used to be a enjoyment
    account it. Glance advanced to more delivered agreeable from you!
    However, how can we keep in touch?

  42. What i do not understood is actually how you’re now not really a lot more smartly-favored than you might be now.
    You are very intelligent. You realize therefore considerably with regards to this matter, produced me in my
    opinion believe it from numerous numerous angles. Its like men and women don’t seem to
    be fascinated except it’s one thing to do with Lady gaga!
    Your individual stuffs outstanding. Always handle it up!

  43. Greetings I am so glad I found your web site, I really found you by
    accident, while I was researching on Bing for something else, Anyhow I am
    here now and would just like to say many thanks for a incredible
    post and a all round enjoyable blog (I also love the theme/design), I
    don’t have time to read it all at the minute but I have
    saved it and also added in your RSS feeds, so when I have time I will
    be back to read more, Please do keep up the excellent b.

  44. Good site you have here.. It’s difficult to find high-quality writing
    like yours nowadays. I honestly appreciate people like you!
    Take care!!

  45. What you said was actually very logical. But, what about this?

    what if you wrote a catchier post title? I mean, I don’t
    wish to tell you how to run your blog, however suppose you added a title that
    makes people want more? I mean 【BZOJ 3103】[ONTAK2010] Palindromic Equivalence –
    Qizy's Database is a little boring. You could look
    at Yahoo’s home page and see how they create post headlines to get people to
    open the links. You might add a video or a picture or two to get people interested about what you’ve written. In my opinion, it could bring your website a
    little livelier.

  46. Hello there, I found your website by means of Google while searching for
    a related topic, your website came up, it looks great. I have bookmarked it in my google bookmarks.

    Hello there, just became aware of your weblog thru Google,
    and located that it is truly informative. I
    am gonna watch out for brussels. I’ll be grateful for those who continue this in future.
    Many other people shall be benefited from your writing.
    Cheers!

  47. My developer is trying to convince me to move to .net from PHP.
    I have always disliked the idea because of the costs.
    But he’s tryiong none the less. I’ve been using Movable-type on numerous websites for about a year and am anxious about switching to another platform.

    I have heard fantastic things about blogengine.net.
    Is there a way I can transfer all my wordpress content into it?
    Any help would be greatly appreciated!

发表评论

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