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

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

Integer Partition

问题描述 :

Given n, k, calculate the number of different (unordered) partitions of n such that no part is repeated k or more times.

输入:

First line, number of test cases, T.
Following are T lines. Each line contains two numbers, n and k.

1<=n,k,T<=105

输出:

First line, number of test cases, T.
Following are T lines. Each line contains two numbers, n and k.

1<=n,k,T<=105

样例输入:

4
4 2
4 3
4 4
4 5

样例输出:

2
4
4
5

首先要知道五边形定理是什么东西

它揭示了整数划分的母函数是欧拉函数的倒数,欧拉函数可以通过级数表示

P(x)*phi(x)=1  -> p(n)-p(n-1)-p(n-2)+p(n-5)+p(n-7)……=0

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 100000
#define mod 1000000007
#define ll long long
ll p[N+10];

void init()
{
    p[0]=p[1]=1;
    for(int i=2;i<=N;++i)
    {
        p[i]=0;int x=1;
        for(int k=1,j=1;x>=0;++k,j*=-1)
        {
            x=i-(3*k*k+k)/2;
            if(x>=0) p[i]+=p[x]*j;
            x=i-(3*k*k-k)/2;
            if(x>=0) p[i]+=p[x]*j;
            if(p[i]>=mod||p[i]<0)
                p[i]=(p[i]%mod+mod)%mod;
        }
    }
}

int main ()
{
    init();
    int T;scanf("%d",&T);
    while(T--)
    {
        int n,K;
        scanf("%d%d",&n,&K);
        ll ans=p[n];
        int x=1;
        for(int k=1,j=-1;x>=0;++k,j*=-1)
        {
            x=n-(3*k*k+k)/2*K;
            if(x>=0) ans+=p[x]*j;
            x=n-(3*k*k-k)/2*K;
            if(x>=0) ans+=p[x]*j;
            if(ans>=mod||ans<0)
                ans=(ans%mod+mod)%mod;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

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

参考:http://blog.csdn.net/jackyguo1992/article/details/9870155