【hdu 4658】Integer Partition (无序分拆数、五边形数定理)

题意

题解

代码

代码语言：javascript复制

int n,k;
int B[N]={1,1,2};
int main() {
	int t;
	sf(t);
	for(int i=3;i<N;  i)
	for(int j=1,f=1;f;  j)
	for(int k=-1;k<2;k =2){
		int w=(3*j*j k*j)/2;
		if(w>i){f=0;break;}
		if(j%2)B[i]=(B[i] B[i-w])%mod;
		else B[i]=(B[i]-B[i-w] mod)%mod;
	}
	while(t--){
		sf(n);sf(k);
		int ans=0;
		ans=B[n]%mod;
		for(int i=1,f=1;f;  i)
		for(int j=-1;j<2&&f;j =2){
			int w=(3*i*i j*i)/2;
			if(w*k>n){f=0;break;}
			if(i%2==0)ans=(ans B[n-w*k])%mod;
			else ans=(ans-B[n-w*k] mod)%mod;
		}
		printf("%dn",ans);
	}
	return 0;
}

integer

0 人点赞