题目传送门: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; }
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.
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!
哇塞,居然是沙发?留个名
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!
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.
This is a topic which is close to my heart… Take care! Exactly where are your contact
details though?
I was able to find good info from your content.
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?
Hi there colleagues, its enormous article on the topic of
cultureand entirely defined, keep it up all the time.
What’s up to all, how is everything, I think every one is getting more from this web page, and your views are good for new visitors.
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.
Quality posts is the secret to invite the visitors to
go to see the website, that’s what this web page is
providing.
If some one wishes to be updated with most recent technologies afterward he must be
pay a visit this site and be up to date every
day.
Great post.
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.
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.
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
Why users still use to read news papers when in this technological world everything is accessible on net?
Pretty nice post. I just stumbled upon your blog and wanted
to say that I’ve truly enjoyed browsing your blog posts.
After all I will be subscribing to your rss feed and I hope you write again soon!
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!
Your mode of explaining everything in this piece of writing is truly nice,
all be able to simply understand it, Thanks a lot.
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
Appreciate the recommendation. Let me try it out.
Hi every one, here every one is sharing these know-how,
thus it’s pleasant to read this web site, and I used to go to see this webpage everyday.
For the reason that the admin of this web site is working, no question very shortly it will be famous, due to its feature contents.
Hi to all, it’s really a pleasant for me to visit this web site, it contains priceless Information.
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.
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.
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.
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.
What’s up, its nice article concerning media
print, we all understand media is a great source of data.
natalielise pof
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
Thank you for sharing your info. I really appreciate your efforts and I will be waiting
for your next post thank you once again.
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. . . . . .
Do you have any video of that? I’d like to find out some
additional information.
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!!
I always used to study article in news papers but now as I am a user of
net thus from now I am using net for content, thanks
to web.
Hey there! Do you know if they make any plugins to protect against hackers?
I’m kinda paranoid about losing everything I’ve worked hard on. Any
suggestions?
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
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.
Every weekend i used to visit this website, as
i wish for enjoyment, since this this website conations actually good
funny material too.
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?
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!
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.
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!
Informative article, just what I needed.
I’m gone to say to my little brother, that he should also pay a visit this webpage on regular basis
to obtain updated from latest information.
You should be a part of a contest for one of the greatest sites on the web.
I will recommend this website!
Great article.
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!
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.
Hi there to all, how is the whole thing, I think every
one is getting more from this website, and your views are good in favor of new
visitors.
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.
I visited multiple web pages but the audio quality for audio songs present at this site
is really fabulous.
Peculiar article, exactly what I needed.
I’ve read some just right stuff here. Definitely price bookmarking for revisiting.
I wonder how much effort you put to create the sort of magnificent informative web
site.
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!
What a stuff of un-ambiguity and preserveness of precious
familiarity on the topic of unexpected emotions.
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.
I think the admin of this web site is truly working hard for his site,
because here every data is quality based material.
Ahaa, its fastidious discussion about this post at this place at this webpage, I have read all
that, so now me also commenting at this place.
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!!
I’m curious to find out what blog platform you’re working with?
I’m having some minor security issues with my latest site
and I would like to find something more risk-free.
Do you have any recommendations?
Thanks designed for sharing such a pleasant thought, paragraph is good,
thats why i have read it fully
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!
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.
Pretty! This has been a really wonderful article.
Thank you for supplying this information.
Your style is so unique compared to many other people. Thank you for publishing when you have the opportunity,Guess I will just make this bookmarked.2
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!
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..
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.
I every time spent my half an hour to read this weblog’s content
daily along with a mug of coffee.
It’s hard to find knowledgeable people in this particular topic, but you seem like you know what you’re talking about!
Thanks
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!
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!
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!
Greetings! Very helpful advice on this article! It is the little changes that make the biggest changes. Thanks a lot for sharing!
I cannot thank you enough for the post.Thanks Again. Much obliged.
Major thanks for the article.Really looking forward to read more. Really Great.