Integer Partition（hdu4658）2013 Multi-University Training Contest 6 整数拆分二

Integer Partition

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 524 Accepted Submission(s): 238

Problem Description

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

Input

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

1<=n,k,T<=10⁵

Output

T lines, each line contains answer to the responding test case.
Since the numbers can be very large, you should output them modulo 10⁹+7.

Sample Input

Sample Output

Source

2013 Multi-University Training Contest 6

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

题意：问一个数n能被拆分成多少种方法，且每一种方法里数字重复个数不能超过k（等于k）。

五边形数定理续，结合上一题（hdu4651），先打表，然后把大于k的个数剪掉；

Integer Partition（hdu4658）2013 Multi-University Training Contest 六整数拆分二

好吧，再啰嗦一遍：

用了五边形数定理以及生成函数，然而我看懂了生成函数怎么搞这题却不知道为啥生成函数是五边形数形式= =

首先观察下面的图片：

Integer Partition（hdu4658）2013 Multi-University Training Contest 六整数拆分二

很容易我们可以发现用这种方式构造N个五边形（假设一个点也算一个五边形），需要点的个数为：

n * ( 3 n - 1 ) 2

接下来我们来看一下数拆分。
提问：将一个正整数N拆成不少于一个数的和，问有多少种方案。

很容易我们可以构造一个多项式：
P(x)=(1+x1+x2+...)(1+x2+x4+...)(1+x3+x6+...)...
=Px(0)x0+Px(1)x1+Px(2)x2+...+Px(n)xn

可以发现N的数拆分的方案数正对应着多项式展开后xn的系数Px(n)

考虑如下等式：

(1 + x 1 + x 2 + . . .) = 1 1 - x

因此我们有：

\prod i = 0 \infty 1 1 - x i = \sum i = 0 \infty P x (i) x i

其中上式等式左边是欧拉函数

ϕ(x)的倒数。即：

1 ϕ ( x ) = \sum i = 0 \infty P x (i) x i

欧拉函数ϕ(x)的展开式为：

ϕ (x) = (1 - x) (1 - x 2) (1 - x 3) . . . = 1 - x - x 2 + x 5 + x 7 - x 12 - x 15 + x 22 + x 26 - . . .

其中的x的指数正对应着广义五边形数！

n	0	1	-1	2	-2	3	-3	4	-4	…
P(n)	0	1	2	5	7	12	15	22	26	…

现在我们要计算Px(n)，由于1ϕ(x)=P(x)，亦即ϕ(x)P(x)=1。

(1 - x - x 2 + x 5 + . . .) (P x (0) + P x (1) x + P x (2) x 2 + P x (3) x 3 + . . .) = 1

所以：

Px(n)=Px(n−1)+Px(n−2)−Px(n−5)−Px(n−7)+...

由于对于满足i(3i−1)2≤n的i的个数不超过(√n)个，于是计算所有Px(n)的复杂度为O(n(√n))

上面我们说明的是不带限制的数拆分，现在我们给定一个限制：拆分出来的每种数的个数不能大于等于k（这也是本题的要求）。

类似的，我们考虑生成函数：

(1 + x 1 + x 2 + . . . + x k - 1) (1 + x 2 + x 4 + . . . x 2 (k - 1)) . . . = \prod i = 0 \infty 1 - x k i 1 - x i = ϕ ( x k ) ϕ ( x ) = ϕ (x k) P (x)

展开

ϕ(xk)得：

(1 - x k) (1 - x 2 k) (1 - x 3 k) . . . = 1 - x k - x 2 k + x 5 k + x 7 k - x 12 k - x 15 k + . . .

然后可得：

ϕ (x k) P (x) = (1 - x k - x 2 k + x 5 k . . .) (P x (0) + P x (1) x + P x (2) x 2 + P x (3) x 3 + . . .)

令

Fk(n)表示n的满足数拆分时每种数的个数小于等于k的数拆分方案数。则有：

F k (n) = P x (n) - P x (n - k) - P x (n - 2 k) + P x (n - 5 k) + . . .

一开始超时了，不然把取余的部分修改了下就过了。。。

卡过啊！

转载请注明出处：http://blog.****.net/u010579068

#include<iostream>
#include<cstdio>
#define NN 100005
#define LL __int64
#define mod 1000000007

using namespace std;
LL wu[NN],pa[NN];
void init()
{
    pa[0]=1;
    pa[1]=1;
    pa[2]=2;
    pa[3]=3;
    LL ca=0;
    for(LL i=1; i<=100000/2; i++)
    {
        wu[ca++]=i*(3*i-1)/2;
        wu[ca++]=i*(3*i+1)/2;
        if(wu[ca-1]>100000) break;
    }
    for(LL i=4; i<=100000; i++)
    {
        pa[i]=(pa[i-1]+pa[i-2])%mod;
        ca=1;
        while(wu[2*ca]<=i)
        {
            if(ca&1)
            {
                pa[i]=(pa[i]-pa[i-wu[2*ca]]);
                pa[i]=(pa[i]%mod+mod)%mod;
                if(wu[2*ca+1]<=i)
                    pa[i]=(pa[i]-pa[i-wu[2*ca+1]]),pa[i]=(pa[i]%mod+mod)%mod;
            }
            else
            {
                pa[i]=(pa[i]+pa[i-wu[2*ca]]);
                pa[i]=(pa[i]%mod+mod)%mod;
                if(wu[2*ca+1]<=i)
                    pa[i]=(pa[i]+pa[i-wu[2*ca+1]]),pa[i]=(pa[i]%mod+mod)%mod;
            }
            ca++;
        }
    }
}
LL work(int n,int k)
{
    LL ans=pa[n];
    LL ca=0;
    while(k*wu[2*ca]<=n)
    {
        if(ca&1)
        {
            ans=(ans+pa[n-k*wu[2*ca]]);
            ans=(ans%mod+mod)%mod;
            if(k*wu[2*ca+1]<=n)
                ans=(ans+pa[n-k*wu[2*ca+1]]),ans=(ans%mod+mod)%mod;
        }
        else
        {
            ans=(ans-pa[n-k*wu[2*ca]]);
            ans=(ans%mod+mod)%mod;
            if(k*wu[2*ca+1]<=n)
                ans=(ans-pa[n-k*wu[2*ca+1]]),ans=(ans%mod+mod)%mod;
        }
        ca++;
    }
    return ans;
}
int main()
{
    int T,n,k;
    init();
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&k);
        printf("%I64d\n",work(n,k));
    }
    return 0;

}

Integer Partition（hdu4658）2013 Multi-University Training Contest 六 整数拆分二

Integer Partition

相关推荐

Integer Partition（hdu4658）2013 Multi-University Training Contest 六整数拆分二