题目传送门：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1806
数据生成器：http://paste.ubuntu.com/23358513/
这题知道Prufer编码的同学都能一眼秒吧？
就是裸的Prufer加上容斥。
但这题细节比较多，我说说我被坑的两个地方吧：
1）可能有多个限制条件针对一个点，在容斥的时候要排除这种情况
2）容斥的时候，所有点的度都确定了，但度数不等于n-2的情况容斥也要排除掉
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int M = 20;
const int N = 1000000+9;
const int MX = 1000000;
const int MOD = 1000000007;
int POW[N],REV[N],lim[M],id[M],n,m,vout,vis[N];
set<pair<int,int> > S;
inline int read(){
char c=getchar(); int ret=0,f=1;
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;
}
inline int pow(int w, int t) {
if (!w || t <= 0) return 1; int ret = 1;
while (t) {
if (t & 1) ret = (LL)ret * w % MOD;
w = (LL)w * w % MOD; t >>= 1;
} return ret;
}
inline int C(int x, int y) {
int ret = (LL)POW[y] * REV[x] % MOD;
return (LL)ret * REV[y-x] % MOD;
}
void DFS(int t, int tot, int cnt, int sol, int f) {
if (tot < 0 || (tot > 0 && cnt == n)) return;
else if (t >= m + 1) {
if (!cnt) return;
else {
sol = (LL)sol * pow(n - cnt,tot) % MOD;
vout = ((vout + f*sol) % MOD + MOD) % MOD;
}
} else {
DFS(t+1, tot, cnt, sol, f);
if (!vis[id[t]]) {
vis[id[t]] = 1;
DFS(t+1, tot - lim[t], cnt + 1, (LL)sol * C(lim[t],tot) % MOD, -f);
vis[id[t]] = 0;
}
}
}
int main(){
n = read(); m = read();
for (int i=1;i<=m;i++) {
id[i] = read(), lim[i] = read() - 1;
if (S.count(make_pair(id[i],lim[i]))) {
i--; m--;
} else {
S.insert(make_pair(id[i],lim[i]));
}
}
POW[1] = REV[1] = POW[0] = REV[0] = 1;
for (int i=2;i<=MX;i++) POW[i] = (LL)POW[i-1] * i % MOD;
REV[MX] = pow(POW[MX], MOD - 2);
for (int i=MX-1;i;i--) REV[i] = (LL)REV[i+1] * (i + 1) % MOD;
vout = pow(n, n-2);
DFS(1,n-2,0,1,1);
printf("%d\n",vout);
return 0;
}
If some one wishes expert view on the topic of blogging then i
advise him/her to visit this webpage, Keep up the fastidious work.
Woah! I’m really digging the template/theme
of this website. It’s simple, yet effective. A lot of times it’s hard to get that “perfect balance” between usability and visual appeal.
I must say that you’ve done a very good job with this.
Also, the blog loads very fast for me on Chrome. Exceptional
Blog!
Hmm it looks like your website ate my first comment (it was extremely long) so I guess I’ll just sum it up what
I wrote and say, I’m thoroughly enjoying your blog. I
too am an aspiring blog writer but I’m still new to the whole thing.
Do you have any tips and hints for beginner blog writers?
I’d definitely appreciate it.
Yes! Finally someone writes about gamefly free trial.
Good day I am so excited I found your blog, I really found you by mistake, while I
was looking on Aol for something else, Anyways I am here now and would
just like to say thank you for a marvelous post and a all round
entertaining blog (I also love the theme/design), I don’t have time
to go through it all at the moment but I have saved it and also
included your RSS feeds, so when I have time I will be back to read
a lot more, Please do keep up the superb job.
I loved as much as you will receive carried out right here.
The sketch is tasteful, your authored material stylish.
nonetheless, you command get bought an edginess over that you wish be delivering the following.
unwell unquestionably come further formerly again as exactly the same nearly very often inside case you shield this hike.
Good day! I know this is kinda off topic but I was wondering which blog platform are you using for this website?
I’m getting sick and tired of WordPress because I’ve had issues with hackers and
I’m looking at options for another platform. I would be fantastic if you
could point me in the direction of a good platform.
I think the admin of this site is truly working hard for his website,
since here every material is quality based stuff.
I was curious if you ever thought of changing the page layout of
your site? Its very well written; I love what youve got to say.
But maybe you could a little more in the way of content so people
could connect with it better. Youve got an awful lot of text for only having 1 or 2
pictures. Maybe you could space it out better?
This post is actually a pleasant one it assists new the web people,
who are wishing in favor of blogging.
An interesting discussion is worth comment. There’s no
doubt that that you ought to write more on this subject matter, it might not be a
taboo subject but usually people do not speak about such topics.
To the next! Many thanks!!
I have to thank you for the efforts you’ve put in writing this
website. I’m hoping to view the same high-grade
blog posts by you in the future as well. In fact, your creative writing abilities has inspired
me to get my very own site now 😉
Very nice post. I just stumbled upon your blog and wished to say that I’ve truly loved surfing around your weblog posts.
In any case I will be subscribing to your feed and I’m hoping you
write once more soon!
It’s going to be finish of mine day, except before finish I
am reading this fantastic article to increase my experience.
Ahaa, its nice dialogue regarding this article at this place at this blog, I
have read all that, so now me also commenting at this place.
It is the best time to make some plans for the
future and it’s time to be happy. I have read this post and if I could I wish to suggest you few interesting things or tips.
Maybe you could write next articles referring to this article.
I desire to read even more things about it! natalielise pof
Aw, this was a really good post. Taking the time and actual effort to create a very good article… but what can I say… I
put things off a whole lot and don’t seem to get
anything done.
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 magnificent information I was looking for this information for my mission.
At this time it appears like Movable Type is the best blogging platform
available right now. (from what I’ve read) Is that what you are
using on your blog?
Have you ever considered writing an ebook or guest authoring on other blogs?
I have a blog based on the same ideas you discuss and would love to have you share some stories/information. I know my readers would
enjoy your work. If you are even remotely interested, feel free to send me an e mail.
natalielise pof
This design is incredible! You most 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!) Fantastic job.
I really enjoyed what you had to say, and more than that, how
you presented it. Too cool!
Hi there! Do you know if they make any plugins to assist with Search Engine Optimization? I’m trying to get my blog to rank for some targeted keywords but I’m not seeing very good
gains. If you know of any please share. Thanks!
Unquestionably believe that which you said.
Your favourite justification appeared to be on the
web the simplest thing to be mindful of. I say to you, I definitely get irked
while people consider concerns that they plainly
do not recognise about. You controlled to hit the nail upon the top as neatly as outlined out
the whole thing with no need side-effects , other folks could take
a signal. Will probably be again to get more. Thanks natalielise pof
Actually when someone doesn’t know then its up to other viewers that they will assist, so here it occurs.
What’s Happening i am new to this, I stumbled upon this I have discovered It positively useful and it has aided me out
loads. I am hoping to give a contribution & assist other customers like its aided me.
Great job.
Excellent post. I was checking continuously this blog and I’m impressed!
Very helpful information specially the last part
🙂 I care for such information a lot. I was looking for this particular information for a very long time.
Thank you and best of luck.
I pay a visit every day a few web pages and blogs to read content, but this blog offers feature based content.
My partner and I stumbled over here coming
from a different web address and thought I should check things out.
I like what I see so i am just following you. Look forward to finding out about your web page
yet again.
Great blog you have here.. It’s difficult to find good quality writing like yours these
days. I seriously appreciate individuals like you!
Take care!!
Have you ever considered writing an ebook or guest authoring on other blogs?
I have a blog centered on the same subjects you discuss and would love to have you share some stories/information. I know my
subscribers would appreciate your work. If you are even remotely
interested, feel free to send me an email.
Everything is very open with a clear clarification of the issues.
It was truly informative. Your website is very helpful. Thank you for sharing!
I think the admin of this web site is in fact working hard in favor of his web page, because here every stuff is quality based material.
Hi there! I simply would like to offer you a big thumbs up
for the excellent info you have right here on this post.
I will be returning to your blog for more soon.
Excellent beat ! I would like to apprentice while
you amend your website, how can i subscribe for a blog website?
The account helped me a acceptable deal. I had been a little
bit acquainted of this your broadcast provided bright clear idea
I like the valuable info you provide in your articles.
I will bookmark your blog and check again here frequently.
I am quite sure I’ll learn many new stuff right here!
Good luck for the next!
Greetings! Very helpful advice within this post!
It is the little changes which will make the largest changes.
Many thanks for sharing!
Woah! I’m really loving the template/theme of this website.
It’s simple, yet effective. A lot of times it’s difficult to get
that “perfect balance” between usability and visual
appeal. I must say you have done a excellent job with this.
In addition, the blog loads super quick for me on Internet explorer.
Exceptional Blog!
Wow that was odd. I just wrote an very long comment but after I clicked submit my comment didn’t appear.
Grrrr… well I’m not writing all that over again. Anyways, just wanted to say superb blog!
Please let me know if you’re looking for a author for your blog.
You have some really great articles and I feel I would be a
good asset. If you ever want to take some of the load off,
I’d love to write some articles for your blog in exchange for a link back to mine.
Please shoot me an email if interested. Thank you!
Hi there to every , as I am really keen of reading this weblog’s post to be updated on a regular
basis. It contains good data.
Great blog you’ve got here.. It’s hard to find excellent writing like yours
nowadays. I truly appreciate people like you!
Take care!!
Spot on with this write-up, I really believe this web site needs
far more attention. I’ll probably be returning to see more,
thanks for the advice!
I’m not that much of a internet reader to be honest but your blogs
really nice, keep it up! I’ll go ahead and bookmark your site to come
back later. Many thanks
My brother suggested I might like this blog.
He was entirely right. This post actually made my day.
You can not imagine just how much time I had spent for this information! Thanks!
Appreciating the time and energy you put into your blog
and in depth information you offer. It’s great to come across a blog every once in a while that isn’t the same outdated rehashed material.
Excellent read! I’ve saved your site and I’m adding your RSS feeds
to my Google account.
I like the helpful information you provide in your articles.
I’ll bookmark your weblog and test again right here frequently.
I am relatively sure I’ll be informed many new stuff right right here!
Good luck for the following!
Please let me know if you’re looking for a article author for your site.
You have some really great articles and I
feel I would be a good asset. If you ever want to take
some of the load off, I’d love to write some material for your blog in exchange for a link back to mine.
Please send me an email if interested. Many thanks!
Simply desire to say your article is as amazing.
The clarity on your publish is simply excellent and that i can assume you’re knowledgeable on this subject.
Fine along with your permission let me to seize your feed to keep up to date with imminent post.
Thank you 1,000,000 and please keep up the rewarding work.
Hi to every one, it’s actually a fastidious for me to pay a visit this web
site, it consists of helpful Information.
Thanks for some other wonderful article. Where else may just anyone get
that kind of info in such a perfect way of writing? I’ve a presentation next week, and I
am at the look for such info.
Everything is very open with a very clear explanation of the issues.
It was definitely informative. Your website is very helpful.
Thank you for sharing!
I am not certain the place you are getting your information, but good topic.
I needs to spend some time finding out much more or figuring out more.
Thank you for magnificent information I was searching for this information for my mission.
This website truly has all the information and facts I needed concerning this subject and
didn’t know who to ask.
You need to be a part of a contest for one of the finest
sites on the web. I will highly recommend this web site!
It is the best time to make some plans for the future and
it is time to be happy. I have read this post and if I could I want to
suggest you some interesting things or tips. Maybe you can write next articles referring to this article.
I desire to read even more things about it!
I like what you guys tend to be up too. This sort of
clever work and reporting! Keep up the superb works guys I’ve
incorporated you guys to my blogroll.
Hello, i think that i noticed you visited my weblog
thus i got here to return the favor?.I’m trying to find
things to enhance my website!I assume its ok to use some of your ideas!!
I really like your blog.. very nice colors & theme.
Did you create this website yourself or did you hire someone to do it for
you? Plz answer back as I’m looking to create
my own blog and would like to find out where u got this from.
kudos
I’m not that much of a online reader to be honest
but your sites really nice, keep it up! I’ll go ahead and bookmark your
website to come back later on. Cheers
Undeniably believe that which you stated. Your favorite reason seemed to be
on the internet the simplest thing to be aware of.
I say to you, I certainly get annoyed while people think about worries that they just
don’t know about. You managed to hit the nail upon the top and defined out the whole thing without having side-effects ,
people could take a signal. Will probably be back to get more.
Thanks
It’s very simple to find out any topic on web as compared to textbooks, as I found this article
at this website.
Hiya, I’m really glad I’ve found this information. Nowadays bloggers publish just about gossips and web and this is really irritating. A good website with exciting content, that is what I need. Thanks for keeping this web-site, I will be visiting it. Do you do newsletters? Cant find it.
Please let me know if you’re looking for a article author for your blog.
You have some really great posts and I think I would be
a good asset. If you ever want to take some of the load off,
I’d really like to write some material for your blog in exchange for a link back to mine.
Please send me an email if interested. Regards!
I seriously love your blog.. Very nice colors & theme.
Did you develop this website yourself? Please reply back as
I’m hoping to create my own site and would like to find out where you got this
from or exactly what the theme is called. Thanks!
It’s very trouble-free to find out any topic on net
as compared to textbooks, as I found this article at this web page.
I was recommended this website by my cousin. I’m not sure whether this post is written by him
as nobody else know such detailed about my difficulty.
You’re amazing! Thanks!
I was recommended this web site by means of my cousin. I’m now not sure whether or not this
put up is written via him as nobody else recognize such distinct approximately my difficulty.
You’re amazing! Thanks!
A motivating discussion is worth comment. I think that you ought to publish more about
this topic, it might not be a taboo matter but typically people do
not speak about these topics. To the next! Many
thanks!!
Thanks for sharing your thoughts on sling tv.
Regards
Its like you read my mind! You appear to know so much about this, like you wrote the book
in it or something. I think that you can do with a few pics
to drive the message home a little bit, but other than that, this is wonderful blog.
An excellent read. I’ll definitely be back.
I constantly spent my half an hour to read this web site’s articles daily along with a
cup of coffee.
Howdy I am so delighted I found your web site, I really found you by error, while I was searching on Askjeeve for something else, Nonetheless I am here now and would just like to say thanks for a fantastic post
and a all round exciting blog (I also love the theme/design), I don’t have time to go through
it all at the moment 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 fantastic work.
I conceive you have remarked some very interesting points, regards for the post.
Really appreciate you sharing this blog article.Much thanks again. Much obliged.
Major thanks for the blog article.Really thank you! Really Cool.