相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4559
神犇题解:http://blog.lightning34.cn/?p=286
解题报告
仍然是广义容斥原理
可以推出$\alpha(x)={{n-1}\choose{x}} \prod\limits_{i=1}^{m}{{{n-1-x}\choose{R_i-1}}\sum\limits_{j=1}^{U_i}{(U_i-j)^{R_i-1}j^{n-R_i}}}$
我们发现唯一的瓶颈就是求$f(i)=\sum\limits_{j=1}^{U_i}{(U_i-j)^{R_i-1}j^{n-R_i}}$
但我们稍加观察不难发现$f(i)$是一个$n$次多项式,于是我们可以用拉格朗日插值来求解
于是总的时间复杂度:$O(mn^2)$
Code
这份代码是$O(mn^2 \log 10^9+7)$的
实现得精细一点就可以把$\log$去掉
#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; }
哇塞,居然是沙发?留个名
Hi, great work. I really appeaciate the data you are providing through your website, i have alwasy find it helpful. Keep up the awsome work.
As I website owner I think the articles here is very superb, thanks for your efforts.
I really like your writing style, wonderful info, regards for putting up :D. “In every affair consider what precedes and what follows, and then undertake it.” by Epictetus.
Hi there, this weekend is pleasant in favor of me, for the reason that this moment i am reading this enormous educational paragraph here
at my house.
After study a number of of the blog posts on your website now, and I actually like your means of blogging. I bookmarked it to my bookmark website record and will probably be checking again soon. Pls try my website as effectively and let me know what you think.
Hello! I know this is kinda off topic but I was wondering if you knew where I could get a captcha plugin for my comment form?
I’m using the same blog platform as yours and I’m having trouble finding one?
Thanks a lot!
We are a group of volunteers and opening a new scheme in our community.
Your web site provided us with valuable info to work on. You have done
a formidable job and our entire community will be
grateful to you.
This is a really good tip especially to those new to the
blogosphere. Brief but very precise information… Thanks
for sharing this one. A must read article!
Hey there! I’m at work surfing around your blog from my new iphone 3gs!
Just wanted to say I love reading your blog and look forward
to all your posts! Carry on the superb work!
You are so awesome! I don’t think I have read through a single
thing like this before. So great to find someone with a few original thoughts on this subject matter.
Seriously.. thank you for starting this up.
This website is one thing that is required on the internet, someone with a little originality!
Hurrah, that’s what I was exploring for, what a stuff!
existing here at this weblog, thanks admin of this website.
773941 903452There is noticeably a bundle to comprehend about this. I assume you created specific good points in functions also. 504231
I’m not sure where you’re getting your information, but good topic.
I needs to spend some time learning much more or understanding more.
Thanks for great info I was looking for this information for my mission.
Right here is the right site for anybody who would like to find out about this topic.
You understand a whole lot its almost hard to argue with you (not that I actually will
need to…HaHa). You definitely put a new spin on a
topic that’s been discussed for years. Excellent stuff, just wonderful!
Hi, its nice piece of writing concerning media print, we
all know media is a fantastic source of facts.
When some one searches for his vital thing, therefore he/she wants to be available
that in detail, so that thing is maintained over here.
Woah! I’m really loving the template/theme of this site. It’s simple, yet
effective. A lot of times it’s very hard to get that “perfect balance” between user friendliness and visual appeal.
I must say you have done a excellent job with this.
Additionally, the blog loads extremely fast for me on Chrome.
Outstanding Blog!
My programmer is trying to convince me to move to .net from PHP.
I have always disliked the idea because of the costs.
But he’s tryiong none the less. I’ve been using WordPress on various websites for about a year and am anxious about
switching to another platform. I have heard fantastic things about blogengine.net.
Is there a way I can transfer all my wordpress posts into it?
Any kind of help would be really appreciated!
I am no longer sure the place you are getting your information, however good topic. I needs to spend some time studying much more or understanding more. Thank you for great information I was in search of this information for my mission.
Today, I went to the beach front with my children. 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!
This is my first time pay a visit at here and i am truly
impressed to read everthing at one place.
Woah! I’m really digging the template/theme of
this blog. It’s simple, yet effective. A lot of times it’s hard to
get that “perfect balance” between superb usability and appearance.
I must say you’ve done a fantastic job with this. In addition, the blog loads super fast
for me on Opera. Superb Blog!
Hi, yup this paragraph is really nice and I have
learned lot of things from it on the topic of blogging.
thanks.
It is truly a nice and helpful piece of info. I am satisfied that you just shared this useful info with us.
Please keep us informed like this. Thank you for
sharing.
We stumbled over here by a different web page and thought I may as well check things out.
I like what I see so now i’m following you. Look forward to exploring your web page repeatedly.
Hello colleagues, how is everything, and what you desire to
say about this article, in my view its truly remarkable designed for me.
These are in fact impressive ideas in about blogging. You have touched some nice factors here.
Any way keep up wrinting.
I genuinely enjoy studying on this website , it contains wonderful articles.
Wonderful blog! I found it while surfing around 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!
Many thanks
What’s Taking place i am new to this, I stumbled upon this I have found It positively useful and it has helped me out loads.
I hope to give a contribution & aid other customers like
its helped me. Great job.