Partition Numbers - Programming Praxis
这个c++程序只能计算到a(121),要算更大的需要用高精度,因为c++高精度要自己写,我就没写了。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define ll long long
using namespace std;
ll dp[200];
ll p(int x){
if(x<0)return 0;
if(x<=1)return 1;
if(dp[x])return dp[x];
int ans=0;
for(int i=1;i<=x;i++){
ans+=(ll)(i%2?1:-1)*(p(x-i*(i*3-1)/2)+p(x-i*(i*3+1)/2));
}
return dp[x]=ans;
}
int main() {
for(int i=1;i<=121;i++)
printf("a(%d)=%lld\n",i,p(i));
return 0;
}
输出: a(1)=1 a(2)=2 a(3)=3 a(4)=5 a(5)=7 a(6)=11 a(7)=15 a(8)=22 a(9)=30 a(10)=42 a(11)=56 a(12)=77 a(13)=101 a(14)=135 a(15)=176 a(16)=231 a(17)=297 a(18)=385 a(19)=490 a(20)=627 ...
突然发现自己非常naive。发现HDU上有原题HDU-4651 Partition,就是求分拆数,题目有要求答案取模。 然后用五边形数定理得到递推式来算。代码如下
#include <cstdio>
#define ll long long
using namespace std;
#define N 100001
const ll M = 1e9+7;
int B[N]={1,1,2};
void get(int i){
for(int j=1;;++j)
for(int k=-1;k<2;k+=2){
int w=(3*j*j+k*j)/2;
if(w>i)return;
if(j%2)B[i]=(B[i]+B[i-w])%M;
else B[i]=(B[i]-B[i-w]+M)%M;
}
}
int t,n;
int main() {
for(int i=3;i<N;++i)
get(i);
scanf("%d",&t);
while(t--){
scanf("%d",&n);
printf("%d\n",B[n]);
}
return 0;
}