见Goolgle
http://zh.wikipedia.org/zh-cn/%E6%95%B4%E6%95%B8%E5%88%86%E6%8B%86
1 /* 2 数学公式 3 ans[i]:i可以有ans[i]种方法得到。（由1-i的数相加） 4 */ 5 #include<stdio.h> 6 typedef long long int64; 7 const int maxn = 100000; 8 const int64 mod = 1000000007; 9 int64 ans[ maxn+15 ]; 10 void init(){ 11 int64 flag,k; 12 ans[ 0 ] = 1; 13 for( int64 i=1;i<=maxn;i++ ){ 14 flag = 1; 15 k = 1; 16 int64 Ans = 0; 17 while( 1 ){ 18 int64 pos1 = (3*k*k-k)/2; 19 int64 pos2 = (3*k*k+k)/2; 20 if( pos1>i ) break; 21 Ans = (Ans+flag*ans[ i-pos1 ]+mod)%mod; 22 if( pos2>i ) break; 23 Ans = (Ans+flag*ans[ i-pos2 ]+mod)%mod; 24 flag = -flag; 25 k++; 26 } 27 ans[ i ] = Ans; 28 } 29 } 30 void test( ){ 31 printf("%d ",13%20); 32 printf("%d ",-13%20); 33 printf("%d ",-13%5); 34 } 35 int main(){ 36 int T; 37 //test(); 38 scanf("%d",&T); 39 init(); 40 while( T-- ){ 41 int n; 42 scanf("%d",&n); 43 printf("%lld ",ans[ n ]); 44 } 45 return 0; 46 }