link : https://loj.ac/problem/6089

 

大致就是第i个物品有i个且每个的体积是i，问填满体积为N的背包的方案数。

 

首先可以发现的是 > sqrt(N) 的物品是用不完的，所以可以看成完全背包。

但直接完全背包的话因为复杂度是 O((N-sqrt(N))*N) 的 ，其实就是 O(N^2)，肯定会挂。

但是我们考虑一个性质:最后背包中的物品最多只能有sqrt(N)件，并且每件的起始体积都是sqrt(N)+1。

所以我们就设 g[i][j] 为选了i件物品，总体积为j的方案数。

转移就是 g[i][j] = g[i-1][j-(sqrt(N)+1)] + g[i][j-i]  ，这就是考虑每次多加一个初始体积物品或者给每个物品都+1的体积。

因为这样能保证后加的物品最后的体积一定<=前加的，所以符合无序性，是正确的。

 

至于<=sqrt(N)的物品直接暴力多重背包就行了 (当然前提是对于每个物品你的多重背包复杂度是 O(N)的，就是对物品体积的同余系下相同的元素一起处理)

 

#include
     
      #define ll long long#define maxn 100005using namespace std;const int ha=23333333;int now,pre,f[2][maxn],n,S;int g[2][maxn],block[maxn];inline int add(int x,int y){	x+=y;	return x>=ha?x-ha:x;}inline void dp_big(){	g[0][0]=1,now=0,block[0]++;		for(int i=1;i*S<=n;i++){		pre=now,now^=1;		fill(g[now],g[now]+i,0);		for(int j=i;j<=n;j++){			g[now][j]=g[now][j-i];			if(j>=S) g[now][j]=add(g[now][j],g[pre][j-S]);						block[j]=add(block[j],g[now][j]);		}	}}inline void dp_small(){	now=0,f[0][0]=1;	for(int i=1,res;i
      
       =0) tmp=add(tmp,ha-f[pre][u-res]);		    	f[now][u]=tmp;			}	}}inline void output(){	int ans=0;	for(int i=0;i<=n;i++) ans=add(ans,f[now][i]*(ll)block[n-i]%ha);	printf("%d\n",ans);}int main(){	scanf("%d",&n),S=sqrt(n)+1;	dp_big();	dp_small();	output();	return 0;}