别人的解题报告：
http://blog.csdn.net/zstu_zlj/article/details/9796087
我的代码：
#include <cstdio>
#define N 100020
const int mod = 1e9+;
int p[N];
void Partition()
{
p[] =;
for(int n=; n <= 1e5; ++n)
{
int fac = ;
int k =;
while(true)
{
int t=n-k*(*k-)/;
if(t < ) break;
p[n] = (p[n]+fac*p[t])%mod;
if(t-k >= )
p[n] = (p[n]+fac*p[t-k])%mod;
p[n] %= mod;
fac = -fac;
++k;
}
p[n] = (p[n]+mod)%mod;
}
}
int main()
{
// freopen("in.cpp","r",stdin);
Partition();
int d;
scanf("%d",&d);
while(d--)
{
int c;
scanf("%d",&c);
printf("%d\n",p[c]);
}
return ;
}
认真考虑二维的情况；n<10^3才可行，而且该代码没有取模操作······
我的代码：
#include <cstdio>
#include <cstring>
#define N 2005
//#define debug
int d[N][N];
void init()
{
for(int i=; i<N; ++i)
d[][i] = d[][i]=d[i][]=d[i][] =;
for(int i=; i<N; ++i)
{
for(int j=; j<N; ++j)
{
if(i-j >= ) d[i][j] += d[i-j][j];
d[i][j] += d[i][j-];
}
}
}
int main()
{
#ifdef debug
freopen("in.c","r",stdin);
#endif
init();
int t;
scanf("%d",&t);
while(t--)
{
int m;
scanf("%d",&m);
printf("%d\n",d[m][m]);
} return ;
}
要查看关于二维的解释可点击下面的链接：