【BZOJ 3612】[HEOI2014] 平衡

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3612
神犇题解:http://blog.csdn.net/Vmurder/article/details/42551603

解题报告

读题后我们发现需要求解这么一个问题:

用$k$个不同的数,来凑成$n$的方案数

这个看起来只能$O(kn^2)$来做$DP$
但我们可以将其优化到$O(nk)$
具体来说,考虑所有$k$个数,一起加或一起减
这样的话,我们就可以不用枚举新加入答案集合的数是哪一个了

回到原题,我们枚举左右两边取出来的重量,和左边用了几块橡皮
然后总的复杂度主要还是在$DP$那一块,复杂度是:$O(k^2n)$的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 100009;
const int M = 11;

int n,K,MOD,f[N][M];

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;
}

int main() {
	for (int T=read(),ans;ans=0,T;T--) {
		n = read(); K = read(); MOD = read();
		memset(f,0,sizeof(f)); f[0][0] = 1;
		for (int i=1,lim=n*K;i<=lim;i++) {
			for (int k=1,LIM=min(i,K);k<=LIM;k++) {
				f[i][k] = (f[i-k][k] + f[i-k][k-1]) % MOD;
				if (i > n) f[i][k] = (f[i][k] - f[i-(n+1)][k-1]) % MOD;
			}
		}
		for (int i=0,lim=n*K;i<=lim;i++) {
			for (int k=0;k<K;k++) {
				ans = (ans + (LL)f[i][k] * f[i][K-k]) % MOD;
				ans = (ans + (LL)f[i][k] * f[i][K-k-1]) % MOD;
			}
		}
		printf("%d\n",(ans+MOD)%MOD);
	}
	return 0;
}

13 thoughts to “【BZOJ 3612】[HEOI2014] 平衡”

  1. Hi, I think your site might be having browser compatibility issues. When I look at your blog in Chrome, it looks fine but when opening in Internet Explorer, it has some overlapping. I just wanted to give you a quick heads up! Other then that, awesome blog!

  2. 429290 752546Sorry for the huge review, but Im genuinely loving the new Zune, and hope this, as nicely as the superb reviews some other folks have written, will support you decide if its the best choice for you. 774456

  3. 770023 171836Heya just wanted to give you a brief heads up and let you know a few with the pictures arent loading properly. Im not sure why but I think its a linking issue. Ive tried it in two different internet browsers and both show exactly the same outcomes. 95714

  4. 864577 456353As I web site possessor I believe the content matter here is rattling magnificent , appreciate it for your hard work. You ought to keep it up forever! Finest of luck. 370430

发表评论

电子邮件地址不会被公开。 必填项已用*标注