HDU 4651 Partition

Problem Description

How many ways can the numbers 1 to 15 be added together to make 15? The technical term for what you are asking is the "number of partition" which is often called P(n). A partition of n is a collection of positive integers (not necessarily distinct) whose sum equals n.

Now, I will give you a number n, and please tell me P(n) mod 1000000007.

Input

The first line contains a number T(1 ≤ T ≤ 100), which is the number of the case number. The next T lines, each line contains a number n(1 ≤ n ≤ 10 ⁵) you need to consider.

Output

For each n, output P(n) in a single line.

Sample Input

4 5 11 15 19

Sample Output

490

整数划分，五边形数定理

#include<iostream>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 200005;
const int base = 1000000007;
int f[maxn], p[maxn], n, T;

void init()
{
  int n = 1000;
  for (int i = 1; i <= n; i++)
  {
    f[i + i - 1] = (i * (i + i + i - 1) >> 1) % base;
    f[i + i] = (i * (i + i + i + 1) >> 1) % base;
  }

  for (int i = p[0] = 1; i < maxn; i++)
  {
    p[i] = 0;
    for (int j = 1, k = -1; i >= f[j]; j++)
    {
      if (j & 1) k *= -1;
      (p[i] += k * p[i - f[j]]) %= base;
    } 
    p[i] = (p[i] + base) % base;
  }
}

int main()
{
  init();
  scanf("%d", &T);
  while (T--) scanf("%d", &n), printf("%d\n", p[n]);
  return 0;
}