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