【BZOJ 4599】[JLOI2016] 成绩比较

相关链接

题目传送门: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;
}

31 thoughts to “【BZOJ 4599】[JLOI2016] 成绩比较”

  1. 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.

  2. 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.

  3. 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!

  4. 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!

  5. 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!

  6. 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!

  7. 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.

  8. 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!

  9. 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!

  10. 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!

  11. 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.

  12. 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!

  13. 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!

  14. 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.

  15. 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

  16. 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.

Leave a Reply to vurtilopmer Cancel reply

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