首页 > ACM题库 > HDU-杭电 > HDU 4651-Partition-数论-[解题报告]HOJ
2015
09-17

HDU 4651-Partition-数论-[解题报告]HOJ

Partition

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

4
5
11
15
19

样例输出:

7
56
176
490

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>
using namespace std;
const int mod=1e9+7;
int f[100010];
void init()
{
    f[0]=1;
    int i,j,k,flag=1;
    for(i=1;i<=100000;i++)
    {
        f[i]=0;
        for(j=1;;j++)
        {
            int t=i-j*(3*j-1)/2;
            int tt=i-j*(3*j+1)/2;
            if(j&1)
                flag=1;
            else
                flag=-1;
            if(t<0&&tt<0)
                break;
            if(t>=0)
                f[i]=(f[i]+flag*f[t])%mod;
            if(tt>=0)
                f[i]=(f[i]+flag*f[tt])%mod;
        }
        f[i]=(f[i]+mod)%mod;
    }
}
int main()
{
    init();
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        cout<<f[n]<<endl;
    }
    return 0;
}
/*
题意:将n拆分成多个正整数之和,问有多少种拆法?
如5=1+1+1+1+1=1+1+1+2=1+1+3=1+4=5=1+2+2=2+3.共7种

Input:
2
100000
99999

Output:
49037875 
677525748

方法:
直接公式:f[n]=∑(-1)^(k-1)*(f[n-k*(3*k-1)/2]+f[n-k*(3*k+1)/2])
            其中n-k*(3*k-1)/2>=0,n-k*(3*k+1)/2>=0;
        注意两个条件要分开判断,有大于0的就加上相应的f,不是两个同时成立或者不成立
*/

//公式原理可见:Partition Function P

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/a601025382s/article/details/9795503