自动搬运

查看原文

来自洛谷，原作者为

	Time_tears oi复健ing

搬运于2025-08-24 22:31:29，当前版本为作者最后更新于2021-06-13 10:50:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

暴力枚举 $s$，然后 $O(nm^2)$ 做完全背包，这样复杂度是 $O(nm^3)$ 的。

注意到可以把 $k$ 的约数的背包先拿出来做了，这样优化了之后我们在后面的背包之中就只用跑剩下的只是 $ks$ 而不是 $k$ 的约数的数，再加上一些卡常就跑的很快了，复杂度不是很会算，$O(可过)$。

#include<bits/stdc++.h>
#define N 2005
using namespace std;
const int mod=1e9+7;
int n,m,K,f[11][N],F[11][N],ans,*A,*B;
inline int Mod(int x) {return x<mod?x:x-mod;}
int main() {
	cin>>n>>m>>K,f[0][0]=1;
	for(int i=1; i<=m; ++i)if(K%i==0)
		for(int k=1; k<=n; ++k)for(int j=i; j<=m; ++j)f[k][j]=Mod(f[k][j]+f[k-1][j-i]);
	for(int s=1; s<=m; ++s) {
		memcpy(F,f,sizeof(f));
		for(int i=1; i<=s; ++i)if((1ll*K*s)%i==0&&K%i!=0)for(int k=1; k<=n; ++k){A=F[k]+i,B=F[k-1];for(int j=i; j<=s; ++j)(*A)=Mod((*A)+(*B)),++A,++B;}
		ans=Mod(ans+F[n][s]);
	} cout<<ans;
	return 0;
}