【BZOJ NOI十连测】KMP

题目传送门:http://begin.lydsy.com/JudgeOnline/problem.php?id=3026
离线版题目:http://paste.ubuntu.com/18022623/
数据生成器:http://paste.ubuntu.com/18021204/
大样例答案:http://paste.ubuntu.com/18022708/
大样例:http://paste.ubuntu.com/18022662/

这是一道很好玩的题目!本来以为是字符串处理题目,结果最后是图论QAQ
很明显,nxt[]实际上是给出了一些字符的等于或不等关系。
如果我们把不等关系用边来表示,那么这货就是一个弦图。
证明的话,也很简单:因为所连的边一定是一条fail链上拓展出来的,所以每一次连边,一定会向所有可能建立关系的点连边
这样的话,不仅仅是一个弦图?还是一个完全图?
然后用完美消除序列倒着求方案数乘一乘就好。(参见本博客的文章《弦图的计数问题》)

更进一步,kmp的构造顺序就是反的完美消除序列。
这个的证明建立在上文提到的“一定会向所有可能建立关系的点连边”,即每一次如果加入了点,那么这个点是一个单纯点
所以直接按照数组顺序乘就可以了QAQ

弦图染色代码:

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

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

const int MAXN = 200000+9;
const LL MOD = 1000000000+7;

int n,c,cnt,fail[MAXN],p[MAXN],Ord[MAXN];
int T,nxt[MAXN],head[MAXN],to[MAXN];
int tot,mx,used[MAXN],pos[MAXN],ord[MAXN];
queue<int> que[MAXN];

inline void AddEdge(int u, int v){
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

inline void MCS(){
	tot = 0; mx = 0;
	for (int i=1;i<=n;i++)
		que[0].push(i);
		
	while (tot < n){
		while (!que[mx].empty()&&used[que[mx].front()]) 
			que[mx].pop();
		if (que[mx].empty()) mx--;
		else {
			int w = que[mx].front(); que[mx].pop();
			ord[++tot] = w; used[w] = 1;
			for (int i=head[w];i;i=nxt[i]) if (!used[to[i]]) 
				que[++pos[to[i]]].push(to[i]), 
				mx = max(mx, pos[to[i]]);
		}
	}
}

int main(){
	n = read(); c = read();
	for (int i=2;i<=n;i++) fail[i] = read();
	
	p[1] = cnt = 1;
	for (int i=1,j;i<n;i++){
		if (fail[i+1]) p[i+1]=p[fail[i+1]];
		else {
			int j = fail[i]; p[i+1]=++cnt;
			while (j) {
				if (Ord[p[j+1]] < i+1 ) 
					AddEdge(p[j+1],p[i+1]), Ord[p[j+1]]=i+1; 
				j=fail[j];
			}
			if (Ord[p[j+1]] < i+1 ) 
				AddEdge(p[j+1],p[i+1]), Ord[p[j+1]]=i+1; 
		}
	}
	
	MCS();
	
	LL vout = 1;
	memset(used,0,sizeof(used));
	for (int j=1,i=ord[j],sum;j<=cnt;i=ord[++j]){
		sum = 0; 
		for (int k=head[i];k;k=nxt[k])
			if (used[to[k]]) sum++;
		sum = c-sum; used[i] = 1;
		vout = (vout*(LL)sum)%MOD;
	}
	printf("%lld\n",vout);
	
	return 0;
}

%%% YJQ 的利用kmp特殊性质的神代码:

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

const LL MOD = 1000000000+7;
const int MAXN = 200000+9;
int n,m,fail[MAXN],go[MAXN];

int main(){
	cin>>n>>m;
	for (int i=2;i<=n;i++)
		scanf("%d",&fail[i]);
	go[0]=1; int ans=m;
	for (int i=1;i<n;i++){
		if (fail[i+1]) go[i] = go[fail[i]];
		else go[i] = go[fail[i]]+1,
		ans = 1LL*ans*(m-go[fail[i]])%MOD;
	}
	printf("%d\n",ans);
	return 0;
}

79 thoughts to “【BZOJ NOI十连测】KMP”

  1. continuously i used to read smaller content which as well clear their motive, and that is also happening with this paragraph which I am reading
    here.

  2. This is the perfect web site for everyone who really wants to understand
    this topic. You realize so much its almost hard to argue with
    you (not that I really would want to…HaHa). You
    definitely put a fresh spin on a subject which has been written about for a long time.
    Great stuff, just great!

  3. Thanks for a marvelous posting! I certainly enjoyed reading it, you could
    be a great author. I will make sure to bookmark your blog and definitely will come
    back in the future. I want to encourage one to continue your
    great job, have a nice day!

  4. Thanks for any other great article. The place else may anybody get that type of info in such an ideal means of
    writing? I’ve a presentation next week, and I’m on the search for
    such information.

  5. Thank you for the good writeup. It in fact was a amusement account it.
    Look advanced to more added agreeable from you! By the way, how can we communicate?

  6. Excellent goods from you, man. I’ve understand your stuff previous to and you’re just extremely magnificent.
    I actually like what you have acquired here, really like what you’re stating and the
    way in which you say it. You make it entertaining and you still care for to keep it smart.
    I cant wait to read much more from you. This is really
    a great web site.

  7. Hey I know this is off topic but I was wondering if you knew of any widgets I could add to my blog that automatically tweet my newest twitter updates.

    I’ve been looking for a plug-in like this for quite some time and was hoping maybe you would have some experience with something like
    this. Please let me know if you run into anything.
    I truly enjoy reading your blog and I look
    forward to your new updates.

  8. An outstanding share! I have just forwarded this onto a colleague
    who had been doing a little homework on this. And he actually bought me lunch because I stumbled
    upon it for him… lol. So allow me to reword this….
    Thank YOU for the meal!! But yeah, thanks for spending time to talk about this
    subject here on your blog.

  9. Excellent beat ! I would like to apprentice while you amend your site,
    how could i subscribe for a blog website? The account helped me a acceptable deal.

    I had been tiny bit acquainted of this your broadcast offered bright clear concept

  10. Howdy would you mind stating which blog platform
    you’re using? I’m looking to start my own blog in the near future but I’m having
    a tough time making a decision between BlogEngine/Wordpress/B2evolution and Drupal.
    The reason I ask is because your design and style seems different
    then most blogs and I’m looking for something completely unique.

    P.S Sorry for getting off-topic but I had to ask!

  11. You really make it seem so easy with your presentation but I find this topic to be actually something that I think
    I would never understand. It seems too complicated and extremely broad
    for me. I’m looking forward for your next post,
    I will try to get the hang of it! plenty of fish natalielise

  12. What’s Going down i am new to this, I stumbled upon this I have found It absolutely helpful and it has aided me out loads.
    I am hoping to contribute & aid other customers like its helped
    me. Good job.

  13. For newest information you have to go to see web and on the web I found this web page as a best web page for hottest updates.

  14. Good post. I learn something totally new and challenging on sites
    I stumbleupon on a daily basis. It will always be
    helpful to read through content from other writers
    and use something from their websites.

  15. I have been surfing online more than 3 hours today,
    yet I never found any interesting article like yours.
    It’s pretty worth enough for me. Personally, if all website owners and bloggers made good content as you did, the web will be much more useful than ever
    before.

  16. That is very attention-grabbing, You’re an excessively professional blogger.
    I’ve joined your rss feed and look forward to in the hunt for more of your excellent post.
    Additionally, I’ve shared your site in my social networks plenty of fish natalielise

  17. Whats up very cool website!! Guy .. Beautiful ..
    Superb .. I will bookmark your web site and take the feeds additionally?
    I am happy to search out so many useful information here in the
    put up, we need develop extra techniques in this regard,
    thank you for sharing. . . . . .

  18. Hello, i think that i saw you visited my weblog so i came to “return the favor”.I’m trying to find things to improve my web site!I suppose its
    ok to use some of your ideas!!

  19. Wonderful blog! I found it while searching on Yahoo News.
    Do you have any suggestions on how to get listed in Yahoo News?
    I’ve been trying for a while but I never seem to get there!
    Appreciate it

  20. Your style is unique in comparison to other people I’ve read stuff from.
    I appreciate you for posting when you have the opportunity, Guess I’ll just bookmark this web site.

  21. Hey there! I just wanted to ask if you ever have any issues with
    hackers? My last blog (wordpress) was hacked and I ended
    up losing many months of hard work due to no backup.

    Do you have any solutions to protect against hackers?

  22. Whats up this is somewhat of off topic but I was wanting to
    know if blogs use WYSIWYG editors or if you have to manually code with HTML.
    I’m starting a blog soon but have no coding skills so I wanted to get guidance from someone
    with experience. Any help would be enormously appreciated!

  23. Thank you for any other informative site. Where else could I get
    that kind of info written in such an ideal means?
    I’ve a challenge that I am just now working on, and I have been at the glance out for
    such info.

  24. Pretty nice post. I simply stumbled upon your blog and wished to mention that I’ve really enjoyed surfing around
    your weblog posts. After all I’ll be subscribing
    in your feed and I hope you write again very soon!

  25. Today, I went to the beach front with my kids. I found a sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put the shell to her ear and screamed.
    There was a hermit crab inside and it pinched her ear.
    She never wants to go back! LoL I know this is entirely off topic but I had to tell someone!

  26. Hey there just wanted to give you a brief heads up and let you know a few of
    the pictures aren’t loading properly. I’m not sure why but I
    think its a linking issue. I’ve tried it in two different browsers
    and both show the same results.

  27. hey there and thank you for your info – I have certainly picked up something new from right here.
    I did however expertise a few technical points using
    this website, as I experienced to reload the web site a lot of times previous to I could get it to load correctly.
    I had been wondering if your web host is OK?
    Not that I am complaining, but sluggish loading instances times will often affect your placement
    in google and could damage your quality score if
    ads and marketing with Adwords. Anyway I’m adding this
    RSS to my email and could look out for a lot more of your respective interesting content.
    Make sure you update this again soon.

  28. Yesterday, while I was at work, my sister stole my iphone and tested to see if it can survive a 40 foot drop, just so
    she can be a youtube sensation. My iPad is now broken and she has 83 views.
    I know this is entirely off topic but I had to share it with someone!

  29. Attractive section of content. I just stumbled upon your site and in accession capital to assert
    that I acquire in fact enjoyed account your blog posts.
    Any way I’ll be subscribing to your feeds and even I achievement you access consistently quickly.

  30. An intriguing discussion is definitely worth comment.
    I do believe that you need to publish more about this subject matter, it may not be
    a taboo subject but generally people don’t speak about such topics.
    To the next! Many thanks!!

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

  32. Ahaa, its fastidious dialogue on the topic of this post here at this web site, I have read all that, so at this time me
    also commenting at this place.

  33. My brother suggested I may like this website. He was once entirely right.
    This publish truly made my day. You can not believe just how a lot time I had
    spent for this information! Thank you!

  34. I am extremely inspired along with your writing talents and also with the layout
    to your weblog. Is this a paid topic or did you modify it your
    self? Either way keep up the excellent quality writing, it’s
    uncommon to peer a great blog like this one these days..

  35. We’re a bunch of volunteers and starting a new scheme in our community.
    Your site provided us with useful info to work on. You have performed a
    formidable activity and our entire community will probably be grateful to you.

  36. First of all I would like to say fantastic blog! I
    had a quick question which I’d like to ask if you don’t mind.
    I was interested to know how you center yourself and clear your thoughts prior to writing.
    I’ve had difficulty clearing my mind in getting my thoughts out.

    I truly do enjoy writing but it just seems like the first 10 to 15 minutes are wasted just trying to
    figure out how to begin. Any suggestions or tips? Cheers!

  37. Wow, incredible weblog format! How long have you ever been blogging for?

    you make running a blog look easy. The total look of
    your website is great, let alone the content material!

  38. Spot on with this write-up, I really feel this website needs
    a great deal more attention. I’ll probably be back again to see
    more, thanks for the advice!

Leave a Reply to ps4 best games ever made 2019 Cancel reply

Your email address will not be published. Required fields are marked *