51 nod-有限リュックカウント問題【dp】

本題
タイトルリンク:http://www.51nod.com/Challenge/Problem.html#problemId=1597
テーマの大意
n n n n種の物品であって、i i番目のi個の大きさはi i i iであり、i i i個である.
ちょうど大きさn n nのリュックサックの方案数を満たすことを求めます
問題を解く構想.
リュックサックを2つに分けることができます.サイズがnsqrt n以下のものについては、n n nsqrt n nn個を超えないので、多重リュックサックで作ることができます.ここでは最適化して、f i,j f_{i,j}fi,jではj%i j%i j%iの違いに基づいてグループ化を行い,グループ内のみが相互に移動可能であり,1つの区間内で移動可能であり,O(n)O(nsqrt n)O(nn)の計算で答えを出すことができ,次いでi i iの1次元を逆列挙圧縮すると方程式がある(u列挙残数f u+p∗i=Σp−i≦k≦p−1 f u+k∗i f_{u+p*i}=sum_{p-i\leq k\leq p-1}f_{u+k*i} fu+p∗i​=p−i≤k≤p−1∑​fu+k∗i​
次に、nsqrt n n nより大きいものについては、無限のものと見なすことができるので、1つの数字を同じでもnsqrt nより大きい数字の和に分解するスキーム数を求めることができる.
1つの集合を考慮すると、1つの数字(物品)n+1sqrt n+1 n+1または全体の数字が+1+1(物品が1つ大きくなる)ずつ加えることができる.
次にg i,j g_{i,j}gi,jは現在の集合内数字と(選択されたものと)i i i,そして集合内数字(物)個数をj j jとすると,方程式g i,j=g i−n−1,j+g i,j−1 g_{i,j}=g_{i−sqrt n−1,j}+g_{i,j−1}gi,j=gi−n−1,j+gi,j−1
そして移行すればいい
c o d e code code

#include
#include
#include
#include
using namespace std;
const int N=1e5+10,XJQ=23333333;
int n,T,f[N],g[2][N],s[N],ans;
int main()
{
	scanf("%d",&n);T=sqrt(n)+1;
	f[0]=1;
	for(int i=1;i<T;i++){
		for(int u=0;u<i;u++){
			int sum=0,t=(n-u)/i;
			for(int p=t;p>max(t-i,-1);p--)
				(sum+=f[u+i*p])%=XJQ; 
			for(int p=t;p>=0;p--){
				if(p-i>=0)sum=(sum+f[u+i*(p-i)])%XJQ;
				sum=(sum-f[u+i*p]+XJQ)%XJQ;
				f[u+p*i]=(f[u+p*i]+sum)%XJQ;
			}
		}
	}
	g[0][0]=s[0]=1;
	for(int i=1;i<T;i++){
		memset(g[i&1],0,sizeof(g[i&1]));
		for(int j=T;j<=n;j++)
			g[i&1][j]=(g[~i&1][j-T]+g[i&1][j-i])%XJQ,
			(s[j]+=g[i&1][j])%=XJQ;
	}
	for(int i=0;i<=n;i++)
		(ans+=1ll*f[i]*s[n-i]%XJQ)%=XJQ;
	printf("%d",ans);
}