参考例题：http://oi.cyo.ng/?p=3191
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 200;
const int MOD = 1000000007;
int n,m,K,r[N],u[N],f[N],g[N],h[N],alpha[N],C[N][N];
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;
}
inline int Pow(int w, int t) {
int ret = 1;
for (;t;t>>=1,w=(LL)w*w%MOD) {
if (t & 1) {
ret = (LL)ret * w % MOD;
}
}
return ret;
}
inline int LagrangePolynomial(int x, int len, int *ff, int *xx) {
int ret = 0;
for (int i=1;i<=len;i++) {
int tmp = ff[i];
for (int j=1;j<=len;j++) {
if (i == j) continue;
tmp = (LL)tmp * (x - xx[j]) % MOD;
tmp = (LL)tmp * Pow(xx[i] - xx[j], MOD-2) % MOD;
}
ret = (ret + tmp) % MOD;
}
return (ret + MOD) % MOD;
}
int main() {
n = read(); m = read(); K = read();
for (int i=1;i<=m;i++) {
u[i] = read();
}
for (int i=1;i<=m;i++) {
r[i] = read();
}
//预处理组合数
C[0][0] = 1;
for (int i=1;i<=n;i++) {
C[i][0] = 1;
for (int j=1;j<=i;j++) {
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}
}
//拉格朗日插值
for (int w=1;w<=m;w++) {
for (int i=1;i<=n+1;i++) {
f[i] = 0; h[i] = i;
for (int j=1;j<=i;j++) {
f[i] = (f[i] + (LL)Pow(i-j, r[w]-1) * Pow(j, n-r[w])) % MOD;
}
}
g[w] = LagrangePolynomial(u[w], n+1, f, h);
}
//广义容斥原理
int ans = 0;
for (int i=K,t=1;i<=n;i++,t*=-1) {
alpha[i] = C[n-1][i];
for (int j=1;j<=m;j++) {
alpha[i] = (LL)alpha[i] * C[n-1-i][r[j]-1] % MOD * g[j] % MOD;
}
ans = (ans + t * (LL)C[i][K] * alpha[i]) % MOD;
}
printf("%d\n",(ans+MOD)%MOD);
return 0;
}
Touche. Solid arguments. Keep up the good spirit.
Amazing! Its genuinely awesome article, I have got much clear idea concerning from this piece of writing.
If some one wishes expert view about blogging afterward i
propose him/her to go to see this webpage, Keep up the fastidious job.
Do you mind if I quote a couple of your posts as long as I
provide credit and sources back to your website?
My blog is in the very same area of interest as
yours and my visitors would definitely benefit from a lot of the information you provide here.
Please let me know if this alright with you. Appreciate it!
Pretty section of content. I just stumbled upon your
blog and in accession capital to assert that I
get actually enjoyed account your weblog posts. Any way I’ll be
subscribing for your feeds and even I fulfillment you access consistently rapidly.
It’s amazing to pay a visit this site and reading the views of all colleagues about this paragraph,
while I am also zealous of getting knowledge.
I was wondering if you ever thought of changing the structure of your blog?
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 one or two pictures. Maybe you could
space it out better?
Aw, this was a really good post. Taking a few minutes and actual effort to make
a good article… but what can I say… I put things off a lot and never seem to get nearly anything done.
Hello! Do you know if they make any plugins to help with Search Engine
Optimization? I’m trying to get my blog to rank for some targeted
keywords but I’m not seeing very good success. If you know of any please share.
Thank you!
Thanks for sharing your info. I truly appreciate your efforts and I will be waiting
for your next write ups thank you once again.
Hi there, You have done an incredible job. I’ll certainly digg it and personally recommend to my friends.
I am sure they will be benefited from this site.
Ahaa, its good discussion regarding this piece of writing
at this place at this web site, I have read all that,
so at this time me also commenting here.
Thankfulness to my father who shared with me concerning this blog,
this web site is genuinely awesome.
At this time I am going away to do my breakfast, afterward having
my breakfast coming again to read other news.
Hi there Dear, are you genuinely visiting this web
site regularly, if so afterward you will definitely get good know-how.
I need to to thank you for this good read!! I certainly loved every little bit
of it. I have got you book marked to look at new things you post…
I all the time used to read article in news papers but now as I am
a user of web so from now I am using net for content,
thanks to web.
Hi there to every one, the contents existing at this website
are genuinely remarkable for people experience, well, keep
up the nice work fellows. pof natalielise
It’s hard to find experienced people in this particular topic,
however, you sound like you know what you’re talking about!
Thanks
Hurrah, that’s what I was searching for, what a information! existing here
at this weblog, thanks admin of this web page.
Hurrah! In the end I got a webpage from where I be able to genuinely obtain valuable
facts concerning my study and knowledge.
You actually make it seem so easy with your presentation but I find this topic to be really
something which I think I would never understand.
It seems too complex and extremely broad for me.
I’m looking forward for your next post, I will try to get the hang of it!
natalielise plenty of fish
Terrific post however , I was wondering if you could write
a litte more on this subject? I’d be very grateful if you could elaborate a
little bit more. Bless you!
naturally like your web-site but you have to test the
spelling on several of your posts. Many of them are rife with spelling
problems and I in finding it very troublesome to tell the truth nevertheless I’ll surely come again again.
I am really loving the theme/design of your site.
Do you ever run into any internet browser compatibility issues?
A number of my blog visitors have complained about my website not operating correctly in Explorer but looks great
in Firefox. Do you have any ideas to help fix this issue?
Very nice post. I just stumbled upon your weblog and wished to say that I
have truly enjoyed browsing your blog posts.
After all I will be subscribing to your rss feed and I hope you write again soon!
What’s up Dear, are you actually visiting this web site on a regular basis, if so after that
you will absolutely obtain nice knowledge.
My spouse and I absolutely love your blog and find nearly
all of your post’s to be exactly what I’m looking for.
Would you offer guest writers to write content for you?
I wouldn’t mind writing a post or elaborating on most of the subjects you write regarding here.
Again, awesome web log!
Very descriptive post, I enjoyed that a lot. Will there be a part 2?
Incredible story there. What occurred after? Thanks!
Thank you for the auspicious writeup. It in fact was a amusement account it.
Look advanced to far added agreeable from you! By the way, how
could we communicate?
Hey there would you mind sharing which blog
platform you’re using? I’m going to start my own blog soon but I’m having
a hard time selecting between BlogEngine/Wordpress/B2evolution and
Drupal. The reason I ask is because your layout seems different then most blogs and I’m looking for something unique.
P.S Apologies for being off-topic but I had to ask!
Simply want to say your article is as surprising. The clarity in your
post is simply great and i can assume you are an expert on this subject.
Well with your permission allow me to grab your feed
to keep up to date with forthcoming post. Thanks a million and please continue the rewarding work.
Appreciate the recommendation. Let me try it out.
Hello, i think that i saw you visited my web site thus i came to “return the
favor”.I am trying to find things to enhance my site!I suppose its ok to use
some of your ideas!!
It’s in fact very difficult in this active life to listen news on TV, therefore I just use the web for that reason, and take the latest information.
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.
Greetings! Very helpful advice in this particular
article! It’s the little changes that produce the largest changes.
Thanks for sharing!
This is a topic that’s near to my heart… Best
wishes! Where are your contact details though?
Since the admin of this site is working, no hesitation very shortly it will be well-known, due to its quality contents.
I’ve been browsing online more than 3 hours today, yet I never found any interesting article like yours.
It’s pretty worth enough for me. In my opinion, if all website owners and
bloggers made good content as you did, the web will be much
more useful than ever before.
Hi there, I found your website via Google
even as searching for a similar matter, your web site got here up, it
seems to be good. I’ve bookmarked it in my google bookmarks.
Hello there, just became aware of your blog via Google,
and located that it’s truly informative. I am going to be careful for brussels.
I will appreciate in case you proceed this in future.
Many folks shall be benefited out of your writing. Cheers!
“Some really nice stuff on this web site , I like it.”
I appreciate you sharing this blog post.Thanks Again. Really Great.
Looking forward to reading more. Great article post.Much thanks again. Keep writing.
Great article.Thanks Again. Keep writing.
Im grateful for the blog post.Really thank you! Will read on…
Hey, thanks for the post.Thanks Again. Really Cool.
Thank you ever so for you blog article. Really Great.
Great blog.Really looking forward to read more. Much obliged.
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.
Very neat blog.Really thank you! Keep writing.
Awesome article.Thanks Again. Will read on…
Fantastic article post.Thanks Again. Great.
Very good blog post.Thanks Again. Great.
wow, awesome blog post.Really thank you! Will read on…
I really enjoy the blog.Really thank you! Really Great.
Awesome post.Thanks Again. Great.
I am so grateful for your blog.Really thank you! Great.
I am so grateful for your blog article. Great.
I value the blog post.Really thank you! Cool.
Thanks for sharing, this is a fantastic article.Thanks Again. Want more.
Fantastic article. Really Great.
Im obliged for the blog article.Really thank you! Awesome.
I loved your article.Thanks Again. Keep writing.
Im thankful for the article.Much thanks again. Much obliged.
Greetings from Los angeles! I’m bored to death at work so I decided to check out your site on my iphone during lunch break.
I enjoy the information you present here and can’t wait to take
a look when I get home. I’m amazed at how fast your blog loaded on my cell phone ..
I’m not even using WIFI, just 3G .. Anyways, amazing blog!
Say, you got a nice blog.Really thank you! Fantastic.
Thanks for the article post. Awesome.
I really liked your article post.Thanks Again. Cool.
Very neat blog article. Much obliged.
Very informative blog article.Thanks Again. Awesome.
Thanks for the blog article.Thanks Again. Awesome.
Great, thanks for sharing this blog.Really thank you! Great.
Im thankful for the article.Really looking forward to read more. Really Great.
Im obliged for the post.Really looking forward to read more. Really Great.
Very informative blog.Much thanks again. Awesome.
I am so grateful for your blog post.Much thanks again. Really Cool.
Im thankful for the blog post.Much thanks again. Fantastic.
Thanks-a-mundo for the blog article. Will read on…
Great blog.Much thanks again. Cool.
A round of applause for your article.Thanks Again. Really Cool.
Very informative blog post.Really thank you! Really Great.
A big thank you for your blog post.Really looking forward to read more. Really Great.
I truly appreciate this blog article.Much thanks again. Much obliged.
Really informative article. Cool.
I truly appreciate this blog article.Really thank you! Fantastic.
Thanks for sharing, this is a fantastic article post. Great.
Great, thanks for sharing this article post. Really Cool.
Thanks for sharing, this is a fantastic blog post.Thanks Again.
Great, thanks for sharing this post. Cool.
Great blog article. Great.
A round of applause for your post.Much thanks again. Will read on…
A round of applause for your blog.Much thanks again. Great.
I value the post.Much thanks again. Fantastic.
Fantastic blog.Thanks Again. Really Great.
Thanks for the blog post. Want more.
Very good blog post. Cool.
Thank you for your blog.Thanks Again. Great.
Im grateful for the article.Really looking forward to read more. Really Cool.
I cannot thank you enough for the article post. Cool.
Thanks so much for the post. Really Cool.
Thanks for the article. Cool.
I loved your blog post.Thanks Again.
A round of applause for your article post.Really looking forward to read more. Much obliged.
wow, awesome blog post. Will read on…
Really enjoyed this article post. Really Great.
I value the blog.Really looking forward to read more. Want more.
Thanks for finally talking about >【模板库】拉格朗日插值法 – Qizy’s Database <Loved it!
Thanks-a-mundo for the blog.Really looking forward to read more. Fantastic.
Very informative blog post. Really Great.
Thanks for the post.Thanks Again. Really Great.
Great blog.Much thanks again. Really Great.
Fantastic blog.Thanks Again. Will read on…
This is one awesome article.Really looking forward to read more. Much obliged.
I am so grateful for your post.Really looking forward to read more. Really Great.
Great, thanks for sharing this post.Much thanks again.
Thanks a lot for the blog post.Really thank you! Keep writing.
I really liked your article.Really thank you! Want more.
Thanks a lot for sharing this with all of
us you actually understand what you are speaking about!
Bookmarked. Please also talk over with my web site
=). We will have a link exchange contract among
us
A big thank you for your blog post.Thanks Again. Really Great.
I cannot thank you enough for the article post.Much thanks again. Much obliged.
Really appreciate you sharing this article.
This is one awesome blog article. Will read on…
Enjoyed every bit of your article post.Really looking forward to read more. Much obliged.
Thanks so much for the blog post.
Great blog article.Thanks Again. Cool.
Very good blog.Really thank you! Keep writing.
I really liked your blog article.Thanks Again. Really Great.
Hmm it looks like your website ate my first
comment (it was super long) so I guess I’ll just sum it up what I submitted
and say, I’m thoroughly enjoying your blog. I as well am an aspiring blog writer but I’m still new to everything.
Do you have any helpful hints for rookie blog writers? I’d really appreciate it.
Looking forward to reading more. Great post.Really thank you! Keep writing.
I really liked your blog.Thanks Again.
Excellent blog you’ve got here.. It’s difficult to find
high quality writing like yours nowadays.
I truly appreciate people like you! Take care!!
Thanks a lot for the article post.Really thank you!
Great, thanks for sharing this blog post. Keep writing.
I appreciate you sharing this post.Thanks Again. Keep writing.
I loved your article post.Really looking forward to read more. Will read on…
Thanks a lot for the article post.Really thank you!
Thank you for your blog post.Really thank you! Really Cool.
Fantastic article.Really looking forward to read more. Really Cool.
Im grateful for the article.Really looking forward to read more. Want more.
I truly appreciate this blog article. Cool.
I cannot thank you enough for the post.Much thanks again. Want more.
I think this is a real great article post.Thanks Again. Cool.
Say, you got a nice blog article.Much thanks again. Want more.
I appreciate you sharing this article. Awesome.
Thanks again for the blog post.Really looking forward to read more.
Thanks a lot for the article.Really looking forward to read more. Will read on…
Really appreciate you sharing this blog article.Thanks Again. Great.
Thank you ever so for you blog post.Really thank you! Will read on…
It’s a shame you don’t have a donate button! I’d certainly donate to this brilliant blog! I guess for now i’ll settle for bookmarking and adding your RSS feed to my Google account. I look forward to new updates and will talk about this website with my Facebook group. Talk soon!
I loved your blog. Much obliged.
Thanks again for the article post.Thanks Again. Really Cool.
Hi there, I found your website via Google whilst searching for a
related topic, your site got here up, it seems to be great.
I have bookmarked it in my google bookmarks.
Hello there, just become aware of your blog via Google, and located
that it’s really informative. I am gonna watch out for brussels.
I will be grateful when you proceed this in future.
Many other people might be benefited from your writing.
Cheers!
Very good article post.Really thank you! Really Great.
Hmm is anyone else having problems with the pictures on this
blog loading? I’m trying to figure out if its a problem on my
end or if it’s the blog. Any feedback would be greatly appreciated.
I loved your blog.Much thanks again. Much obliged.
A round of applause for your post.Really looking forward to read more. Want more.
I am so grateful for your post.Really looking forward to read more. Cool.
I cannot thank you enough for the blog article. Cool.
A round of applause for your article post.Really looking forward to read more. Much obliged.
I think this is a real great blog article.Really thank you! Fantastic.
Really appreciate you sharing this article post.Much thanks again. Really Cool.
Thanks again for the blog.Thanks Again. Really Cool.
A round of applause for your post.Really looking forward to read more. Keep writing.
Really informative blog post. Great.
I really like and appreciate your post.Really looking forward to read more.
Im thankful for the blog post.Really looking forward to read more. Want more.
I think this is a real great blog post.Really looking forward to read more. Keep writing.
Thanks for the post.Really thank you! Cool.
Say, you got a nice article.Really looking forward to read more. Cool.
Why viewers still use to read news papers when in this technological globe the whole thing
is accessible on net?
Very rapidly this website will be famous among all blog visitors, due to it’s fastidious posts
Order health insurers as much as you need, all sizes and quantities are available. Both forms, brand name and generic, are there to choose from. Now buying your medicines is as easy as 1-2-3. The convenience that you will see viagra online canadian pharmacy online is really wonderful.
Wow! This could be one particular of the most beneficial blogs We have ever arrive across on this subject. Basically Wonderful. I am also a specialist in this topic so I can understand your effort.
Major thankies for the blog article.
I do accept as true with all of the ideas you’ve offered in your post. They are very convincing and will definitely work. Still, the posts are very brief for newbies. May just you please lengthen them a little from subsequent time? Thank you for the post.
I value the blog post.
I love your blog.. very nice colors & theme.
Did you design this website yourself or did you hire someone to do it for you?
Plz respond as I’m looking to construct
my own blog and would like to find out where u got this from.
many thanks
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.
This is the right website for anyone who really wants to understand this topic.
You realize a whole lot its almost hard to argue with you (not that I really will
need to…HaHa). You definitely put a brand new spin on a subject which has been discussed
for years. Great stuff, just excellent!
It’s hard to come by well-informed people for this subject, however, you sound like you know what you’re talking about!
Thanks
Very neat article.Really thank you! Great.
You ought to take part in a contest for one of the greatest sites on the web.
I most certainly will highly recommend this website!
We are a gaggle of volunteers and starting a brand new scheme in our community.
Your web site provided us with useful info to work on. You’ve performed
an impressive job and our entire community might be thankful to you.
Remarkable! Its truly remarkable paragraph, I have got much
clear idea regarding from this article.
Very nice post. I simply stumbled upon your blog and wanted to say
that I’ve really enjoyed surfing around your weblog posts.
In any case I will be subscribing for your rss feed and I hope you write once more soon!
Howdy 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 web browsers and both show the
same outcome.
A motivating discussion is worth comment. I think that you ought to publish more about this issue, it may not be a
taboo subject but typically people do not speak about such
subjects. To the next! Kind regards!!
What’s up, I want to subscribe for this webpage to take newest updates, so where can i do
it please help out.
Superb blog! Do you have any suggestions for aspiring writers?
I’m hoping to start my own website soon but I’m a little
lost on everything. Would you advise starting with a free platform like WordPress or go for
a paid option? There are so many options out there that
I’m totally overwhelmed .. Any recommendations?
Thanks!
Link exchange is nothing else except it is only placing the other person’s blog link on your page at proper place and other person will also do similar in favor of you.
Heya i am for the first time here. I found this board and I find It really useful & it helped me out a lot.
I hope to give something back and help others like you aided me.
My partner and I stumbled over here from a different website and thought I might as
well check things out. I like what I see so i am just following you.
Look forward to looking over your web page yet again.
Hello i am kavin, its my first occasion to commenting anyplace, when i read this
paragraph i thought i could also make comment
due to this sensible article.
Admiring the persistence you put into your site and detailed information you present.
It’s nice to come across a blog every once in a while that isn’t the same out of date rehashed information. Great read!
I’ve bookmarked your site and I’m adding your RSS feeds to
my Google account.
My spouse and I absolutely love your blog and find the majority of
your post’s to be exactly I’m looking for. Do you offer
guest writers to write content for you? I wouldn’t mind producing a post or elaborating on a few of the subjects you write in relation to here.
Again, awesome website!
I likewise believe thence, perfectly indited post! .
Definitely imagine that that you said. Your favorite reason appeared to
be at the internet the easiest thing to understand of.
I say to you, I definitely get irked at the same time as
other folks consider issues that they just don’t recognise about.
You controlled to hit the nail upon the top and also defined out the
whole thing with no need side-effects , other people could take a signal.
Will probably be again to get more. Thanks
You have made some decent points there. I looked on the web to learn more about the issue and found most people will go along with your views on this website.
Highly descriptive post, I liked that bit.
Will there be a part 2?
Good day! This is kind of off topic but I need some
advice from an established blog. Is it difficult to set up your own blog?
I’m not very techincal but I can figure things out pretty quick.
I’m thinking about making my own but I’m not sure where to start.
Do you have any tips or suggestions? Appreciate it
First of all I want to say fantastic blog!
I had a quick question in which I’d like to ask if you do not mind.
I was curious to know how you center yourself and clear
your head before writing. I’ve had a hard time clearing my thoughts in getting my
ideas out. I truly do enjoy writing but it just seems like the first 10 to 15 minutes are lost just
trying to figure out how to begin. Any ideas or hints?
Thanks!
Outstanding post however , I was wondering if you could write a litte more on this topic?
I’d be very grateful if you could elaborate a little bit more.
Appreciate it!
There will always be someone who will accompany you to fulfill your unfulfilled wishes, send you flowers, accompany you to watch the sunrise and sunset, accompany you to walk the Yangtze River Bridge to accompany you to play the carousel, and spend the rest of your life with you.
I like the valuable info you provide on your articles.
I will bookmark your blog and test again right
here frequently. I’m somewhat sure I’ll be told lots of new stuff proper right
here! Good luck for the next!
Hurrah! At last I got a weblog from where I can truly
obtain useful data concerning my study and knowledge.
I will immediately grab your rss as I can not find your email subscription hyperlink or e-newsletter service.
Do you’ve any? Please permit me recognize in order that I could subscribe.
Thanks.
My brother suggested I may like this blog. He used to be totally right.
This submit actually made my day. You cann’t consider simply how so much time I had
spent for this information! Thanks!
This design is spectacular! 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!) Wonderful job. I really loved
what you had to say, and more than that, how you presented it.
Too cool!
It’s going to be ending of mine day, except before ending I am reading
this wonderful article to improve my know-how.
Greetings! Very helpful advice on this article! It is the little changes that make the biggest changes. Thanks a lot for sharing!