【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 ——————————
今天我们机房讨论了一下,这货是个弦图,不一定是一个完全图

39 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.

发表评论

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