自动搬运

查看原文

来自洛谷，原作者为

	Goldia 这个家伙太弱了,什么也没有留下

搬运于2025-08-24 22:05:50，当前版本为作者最后更新于2019-10-09 11:15:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

真是一道毒瘤的卡空间题

n^2的dp应该很容易理解

• 111111111
• 1111111
• 1111111
• 1111
• 1

我们很容易可以想到题目要求的数组a就是如上阶梯状的东西，在第一行添加一个数或者新添一行数量为整个阶梯的宽的一行。

• 所以设$f[i][j]$表示当前还剩i个‘1’宽为j的方案数

• $f[i][j]=f[i-1][j-1]$(第一行添加一个数)+$f[i-x][x]$(新添一行数量为整个阶梯的宽的一行);

code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int mod=1e9+7; 
int m,k,cheng[10005],n,f[10005][10005];
int poww(int x,int nn)
{
	int res=1;
	while(nn)
	{
		if(nn&1)res=1ll*res*x%mod;
		x=1ll*x*x%mod;
		nn>>=1;
	}
	return res;
}
int main()
{
	scanf("%d%d%d",&n,&k,&m);
	for(int i=1;i<=10000;i++)
		cheng[i]=poww(i,m);
	for(int i=0;i<=n;i++)
		f[i][i]=1;
	for(int x=1;x<=k;x++)
		for(int i=x;i<=n;i++)
			f[i][x]=(f[i-1][x-1]+f[i-x][x])%mod;
	int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=k;j++)
		{
			int num=0;
			if(i*j<=n)num+=f[n-i*j][k-j];
			ans=(ans+1ll*num*cheng[i]%mod)%mod;
		}
	cout<<ans;
	return 0;
}

但这毒瘤题卡空间 怎么办？

没关系，我们可以用动态开空间的方法过去

$*p=new int [n];$开一段长度为n的数组

$delete []p;$删除数组的空间

然后这题就这样水过去了

code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int mod=1e9+7; 
int m,k,cheng[10005],n,*f[10005];
int poww(int x,int nn)
{
	int res=1;
	while(nn)
	{
		if(nn&1)res=1ll*res*x%mod;
		x=1ll*x*x%mod;
		nn>>=1;
	}
	return res;
}
int ans=0;
int main()
{
	scanf("%d%d%d",&n,&k,&m);
	for(int i=1;i<=n;i++)
		cheng[i]=poww(i,m);
	//for(int i=0;i<=n;i++)f[i][i]=1;
	f[0]=new int[n+k+1];
	for(int i=0;i<=n;i++)
		f[0][i]=0;
	f[0][0]=1;
	for(int j=0;j<k;j++)
	{
		f[j+1]=new int[n+k+1];
		for(int i=0;i<=n;i++)
			f[j+1][i]=0;
		f[j+1][j+1]=1;
		for(int i=j+1;i<=n;i++)
			f[j+1][i]=(f[j][i-1]+f[j+1][i-j-1])%mod;
		for(int i=1;i<=n;i++)
		{
			int num=0;
			if(i*(k-j)<=n)(num+=f[j][n-i*(k-j)])%=mod;
			ans=(ans+1ll*num*cheng[i]%mod)%mod;
		}
		delete []f[j];
		f[j]=0;	
	}
	cout<<ans;
	return 0;
}