[loj6089]小Y的背包计数问题

DP

---

题面

小$Y$有一个大小为$n$的背包，并且小$Y$有$n$种物品。
对于第$i$种物品，共有$i$个可以使用，并且对于每一个$i$物品，体积均为$i$。
求小$Y$把该背包装满的方案数为多少，答案对于$23333333$取模。
定义两种不同的方案为：当且仅当至少存在一种物品的使用数量不同。

• $n\leq10^5$

解析

这个背包问题让我耳目一新啊。
$idea$棒棒的。

注意到题目中物品$i$（$i\geq\sqrt n$)的个数限制实际上是不存在的。
所以可以把这个问题分为两个子问题：多重背包问题和完全背包问题。

设$f[i][v]$表示前$i$个物品，总体积为$v$时的方案数。
对于$i\leq\sqrt n$：（多重背包问题）
很显然有

$$f[i][v]=\sum_{j=1}^if[i-1][v-j*i]$$
可以前缀和优化做到$O(n\sqrt n)$。

对于$i\geq\sqrt n$：（完全背包问题）
又注意到一个物品最多取$\sqrt n$个。
同样设个$g[i][v]$表示方案数。
可以认为我们要$DP$出一个和为$n$，最小数至少$\sqrt n+1$的不下降序列
（序列中的数是物品体积）。
转移有两种：

• 在序列开头加入一个数$\sqrt n+1$
• 把序列中所有数$+1$

则

$$g[i][v]=g[i-1][v-\sqrt n-1]+g[i][v-i]$$
这个复杂度$O(n)$？
最后讨论一下给前一个问题分配多少体积，后一个问题分配多少体积，统计答案即可。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define re register
#define il inline
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=2005,inf=2e9,mod=23333333;
int n,f[N],g[350][N],s[N],ans=-inf,m;
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
int main()
{
  n=gi();m=sqrt(n);
  f[0]=1;
  fp(i,1,m)
    {
      fp(j,0,i) s[j]=f[j];
      fp(j,i,n) s[j]=(f[j]+s[j-i])%mod;//前缀和
      fp(j,0,n)
    {
      f[j]=s[j];
      if(j-i*(i+1)>=0) f[j]=(f[j]-s[j-i*(i+1)]+mod)%mod;//去掉不合法状态
    }
    }
  g[0][0]=1;ans=f[n];
  fp(i,1,m)
    for(re int j=i*(m+1);j<=n;j++)
      {
    g[i][j]=(g[i-1][j-m-1]+g[i][j-i])%mod;
    (ans+=1ll*g[i][j]*f[n-j]%mod)%=mod;
      }
  printf("%d\n",ans);
  return 0;
}