HDU 4651 数论 partition 求自然数的拆分数
别人的解题报告：
http://blog.csdn.net/zstu_zlj/article/details/9796087
我的代码：
1 #include <cstdio> 2 #define N 100020 3 const int mod = 1e9+7; 4 int p[N]; 5 void Partition() 6 { 7 p[0] =1; 8 for(int n=1; n <= 1e5; ++n) 9 { 10 int fac = 1; 11 int k =1; 12 while(true) 13 { 14 int t=n-k*(3*k-1)/2; 15 if(t < 0) break; 16 p[n] = (p[n]+fac*p[t])%mod; 17 if(t-k >= 0) 18 p[n] = (p[n]+fac*p[t-k])%mod; 19 p[n] %= mod; 20 fac = -fac; 21 ++k; 22 } 23 p[n] = (p[n]+mod)%mod; 24 } 25 } 26 int main() 27 { 28 // freopen("in.cpp","r",stdin); 29 Partition(); 30 int d; 31 scanf("%d",&d); 32 while(d--) 33 { 34 int c; 35 scanf("%d",&c); 36 printf("%d ",p[c]); 37 } 38 return 0; 39 }
认真考虑二维的情况；n<10^3才可行，而且该代码没有取模操作······
我的代码：
1 #include <cstdio> 2 #include <cstring> 3 #define N 2005 4 //#define debug 5 int d[N][N]; 6 void init() 7 { 8 for(int i=0; i<N; ++i) 9 d[0][i] = d[1][i]=d[i][0]=d[i][1] =1; 10 for(int i=2; i<N; ++i) 11 { 12 for(int j=2; j<N; ++j) 13 { 14 if(i-j >= 0) d[i][j] += d[i-j][j]; 15 d[i][j] += d[i][j-1]; 16 } 17 } 18 } 19 int main() 20 { 21 #ifdef debug 22 freopen("in.c","r",stdin); 23 #endif 24 init(); 25 int t; 26 scanf("%d",&t); 27 while(t--) 28 { 29 int m; 30 scanf("%d",&m); 31 printf("%d ",d[m][m]); 32 } 33 34 return 0; 35 }