hdu 4651 Partition(整数拆分+五边形数)

时间:2023-03-10 03:18:02
hdu 4651 Partition(整数拆分+五边形数)

Partition

Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 462    Accepted Submission(s): 262

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 ≤ 105) you need to consider.
Output
For each n, output P(n) in a single line.
Sample Input
4
5
11
15
19
Sample Output
7
56
176
490
Source
Recommend
zhuyuanchen520

欧拉函数的倒数是分割函数母函数,亦即:

hdu 4651 Partition(整数拆分+五边形数)生成函数

hdu 4651 Partition(整数拆分+五边形数)   (1)

利用五边形数定理可得到以下的展开式:

hdu 4651 Partition(整数拆分+五边形数) (2)
将(2)式带入(1)式,并乘到(1)式的左边,进行展开,合并同类项,根据非常数项的系数为0!!
 
即将hdu 4651 Partition(整数拆分+五边形数)生成函数配合五边形数定理,可以得到以下的递归关系式
hdu 4651 Partition(整数拆分+五边形数)
 #include<stdio.h>
typedef long long ll;
const int mo=;
ll p[];
void pre()//打表,欧拉函数的倒数是分割函数的母函数!!!
{
p[]=;
for(ll i=;i<=;i++)
{
ll t=,ans=,kk=;
while()
{
ll tmp1,tmp2;
tmp1=(*kk*kk-kk)/;
tmp2=(*kk*kk+kk)/;
if(tmp1>i)break;
ans=(ans+t*p[i-tmp1]+mo)%mo;
if(tmp2>i)break;
ans=(ans+t*p[i-tmp2]+mo)%mo;
t=-t;
kk++;
}
p[i]=ans;
}
}
int main()
{
pre();
int T,n;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
printf("%lld\n",p[n]);
}
}