Algorithm 版 (精华区)

发信人: sino (茶水先生), 信区: Algorithm
标  题: ACM-2.1.1--整数拆分的方案数
发信站: 哈工大紫丁香 (2001年08月06日21:41:03 星期一), 站内信件

题目：整数拆分
     将一个正整数n,拆分成一组小于n的正整数的和（不考虑排列的次序）。
求共有多少组可能的拆分。
|============================================================|
这是我最近看的一个题。
此题可转化为利用母函数求不定方程解的个数的问题。
拆分中不选取1可表示为1 -- 此处指x的0次幂、系数为1。
拆分中选1个1可表示为X
拆分中选2个1可表示为X*X
    .
    .
    .
拆分中选n个1可表示为 X的N次幂
由加法原理得到选取1的所有方案为1+X+X*X+...+X的N次幂;
同理，并由乘法原理得到同时选取1、2、...、N-1 的所有方案为多项式的积：
g(x)=   ( 1 + X +...+ X的N次幂 )*
    ( 1 + X*X + X(4) +...+ X(2[N/2]) )*
    ( 1 + X*X*X + X(6) +...+ X(3[N/3]) )*
        .
        .
    ( 1 + X(r) + X(2r) +...+ X(r[N/r]) )*
        .
        .
    ( 1 + X(N-1) )
g(x)展开式中的X(N)的系数，就是问题的解。
绝对比递归的枚举法快！
    
我写了一段程序，pIII 500上算1--400的结果，用不了1秒钟。
            
            （感谢Darcy指出我的错误！）

// BCB 5
void main()
{
    int  i,j,k;
    const int n=400;
    __int64  a[401],b[401];

    for (i=0;i<=n;i++) b[i]=1;
    for (i=2;i<=n;i++) {
        for (j=0;j<=n;j++) a[j]=b[j];
        for (j=i;j<=n;j+=i)
            for (k=0;k<=n-j;k++) b[j+k]+=a[k];
        printf("\n%d : %Ld",i,b[i]);
    }
}
// |================================================================|
// 参考数据：
//  N   解
//  5   7   
//  10  42
//  50  204226
//  95  104651419   
//  100 190569292   
//  400 6727090051741041926
// |================================================================|


--
撷取生活中每一朵清新的浪花,智慧的浪花 ..汇成音乐的海洋.

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: mtlab4.hit.edu.cn]
※ 修改:·sino 於 08月17日19:17:54 修改本文·[FROM: mtlab4.hit.edu.cn]