hdu4651(广义五边形数 & 分割函数１)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4651

题意：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 对应前面的两个数

代码：

 #include <iostream>

 using namespace std;

 const int mod = 1e9 + ;

 const int MAXN = 1e5 + ;

 int f[MAXN];

 void get_f(void){

     f[] = ;

     for(int i = ; i < MAXN; i++){

         for(int j = , cnt = ; i - ( * j * j - j) /  >= ; j++, cnt *= -){

             int cc =  * j * j;

             f[i] += f[i - (cc - j) / ] * cnt;

             f[i] %= mod;

             f[i] = (f[i] + mod) % mod;

             if(i >= (cc + j) / ){

                 f[i] += f[i - (cc + j) / ] * cnt;

                 f[i] %= mod;

                 f[i] = (f[i] + mod) % mod;

             }

         }

     }

 }

 int main(void){

     get_f();

     int t, x;

     cin >> t;

     while(t--){

         cin >> x;

         cout << f[x] << endl;

     }

     return ;

 }