【LOJ6089】小Y的背包计数问题（动态规划） 【LOJ6089】小Y的背包计数问题（动态规划）
题面
题解
神仙题啊。
我们分开考虑不同的物品，按照编号与(sqrt n)的关系分类。
第一类：(ile sqrt n)
即需要考虑所有的情况，那么设(f[i][j])表示前(i)个物品装了体积(j)的方案数。
显然(f[i][j]=sum_{k=1}^i f[i][j-k*i])转移过来，那么按照(i)分剩余类，前缀和转移即可。
这一部分的复杂度是(O(nsqrt n))
第二类：(ige sqrt n)
因为(i*ige n)，所以这一部分的任何一个物品都不存在个数的限制，即可以随意选择。
那么我们只需要用所有大于(sqrt n)的数做整数划分就行了。
设(g[i][j])表示当前一共划分出来了(i)个数，和为(j)的方案数，每次要么加入一个(sqrt n)，要么把所有数(+1)。
这一部分因为数的共个数，即(i)不会超过(sqrt n)，所以总的复杂度也是(O(nsqrt n))的。
那么这题的总复杂度就是(O(nsqrt n))了。
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
#define ll long long
#define MOD 23333333
#define MAX 100100
int n,m,ans;
int f[350][MAX],g[350][MAX],s[MAX];
int main()
{
cin>>n;m=sqrt(n);
f[0][0]=1;
for(int i=1;i<=m;++i)
{
for(int j=0;j<i;++j)
{
int tot=0;
for(int k=j;k<=n;k+=i)s[++tot]=f[i-1][k];
for(int k=1;k<=tot;++k)s[k]=(s[k-1]+s[k])%MOD;
for(int k=j,tot=0;k<=n;k+=i,++tot)
f[i][k]=(f[i][k]+s[tot+1]-s[max(0,tot-i)]+MOD)%MOD;
}
}
memset(s,0,sizeof(s));g[0][0]=s[0]=1;
for(int i=1;i<=m;++i)
for(int j=0;j<=n;++j)
{
if(j>=i)g[i][j]=(g[i][j]+g[i][j-i])%MOD;
if(j>=m+1)g[i][j]=(g[i][j]+g[i-1][j-(m+1)])%MOD;
s[j]=(s[j]+g[i][j])%MOD;
}
for(int i=0;i<=n;++i)ans=(ans+1ll*s[n-i]*f[m][i])%MOD;
printf("%d
",ans);
return 0;
}