题目链接：

 

题意：f(x) 为将 x 分成其他数和的形式的方案数．对于 t 组输入，输出 f(xi)．

 

思路：直接套公式即可．

1、广义五边形数

qn 为 (3*n*n-n)/2 和 (3*n*n+n)/2

q1 = 1, 2

q2 = 5, 7

q3 = 12, 15

...

2、分割函数

p(n) = sigma(-1)^(i-1)p(n-qi) (qi <= n) //这里的 qi 对应前面的两个数

 

代码：

1 #include 
      
        2 using namespace std; 3  4 const int mod = 1e9 + 7; 5 const int MAXN = 1e5 + 1; 6 int f[MAXN]; 7  8 void get_f(void){ 9     f[0] = 1;10     for(int i = 1; i < MAXN; i++){11         for(int j = 1, cnt = 1; i - (3 * j * j - j) / 2 >= 0; j++, cnt *= -1){12             int cc = 3 * j * j;13             f[i] += f[i - (cc - j) / 2] * cnt;14             f[i] %= mod;15             f[i] = (f[i] + mod) % mod;16             if(i >= (cc + j) / 2){17                 f[i] += f[i - (cc + j) / 2] * cnt;18                 f[i] %= mod;19                 f[i] = (f[i] + mod) % mod;20             }21         }22     }23 }24 25 int main(void){26     get_f();27     int t, x;28     cin >> t;29     while(t--){30         cin >> x;31         cout << f[x] << endl;32     }33     return 0;34 }