hdu 1028

电玩女神 2023-02-26 10:28 14阅读 0赞

![博客图片][format_png]

## 题目链接 ##

[hdu1028][]

## 题目概述 ##

求一个整数 N N N的可重无序拆分.

## 解题思路 ##

稍加变换,原问题等价于方程:  
 1 e 1 + 2 e 2 + 3 e 3 + ⋯ + n e n = n ,   ( e i ≥ 0 , i = 1 , 2 , 3 , …   ) 1e\_1+2e\_2+3e\_3+\\cdots +ne\_n=n,\\,(e\_i \\ge 0, i= 1, 2, 3,\\dots) 1e1\+2e2\+3e3\+⋯\+nen=n,(ei≥0,i=1,2,3,…)  
解的个数,可以看做是将 n n n个相同的小球放到 n n n个相同的盒子允许空盒的数目.对应的结果就是函数:  
 g ( x ) = ( 1 + x + x 2 + x 3 + ⋯   ) ( 1 + x 2 + x 4 + ⋯   ) ⋯ ( 1 + x n + x 2 n + ⋯   ) g(x) = (1+x+x^2+x^3+\\cdots)(1+x^2+x^4+\\cdots)\\cdots(1+x^n+x^\{2n\}+\\cdots) g(x)=(1\+x\+x2\+x3\+⋯)(1\+x2\+x4\+⋯)⋯(1\+xn\+x2n\+⋯)  
展开式中 x n x^n xn项的系数.对于 1 , x i , x 2 i , … 1,x^i,x^\{2i\},\\dots 1,xi,x2i,…可以理解为使用整数 i , 0 , 1 , 2 , … i,0,1,2,\\dots i,0,1,2,…次,得到整数 1 , i , 2 i , …   . 1,i,2i,\\dots. 1,i,2i,….所以展开式中的 x n x^n xn就是 x 1 e 1 , x 2 e 2 , … x^\{1e\_1\},x^\{2e\_2\},\\dots x1e1,x2e2,…相乘,使得 x x x的指数部分之和是 n . n. n.

## 注意 ##

因为这里每一个整数 i i i使用的数量都没有限制,所以写的是 1 , x i , x 2 i , … 1,x^i,x^\{2i\},\\dots 1,xi,x2i,…,假设整数 i i i使用的次数只能是奇数,那么整数 i i i的展开应该是 ( x i + x 3 i + …   ) (x^i+x^\{3i\}+\\dots) (xi\+x3i\+…);或者整数 i i i的使用次数只能是序列 \{ b 1 , b 2 , …   \} \\\{b\_1,b\_2,\\dots\\\} \{ b1,b2,…\}中的,那么 i i i的展开应该是 ( x i b 1 + x i b 2 + …   ) . (x^\{ib\_1\}+x^\{ib\_2\}+\\dots). (xib1\+xib2\+…).

另外注意上面方程前面那个 e i e\_i ei前面的的系数 i i i, e i e\_i ei表示的是使用这个系数多少次,而这个系数表示另外一种约束,可以这样理解,就是使用一个东西必须要使用 i i i次,如果上面的方程变为:  
 e 1 + e 2 + e 3 + ⋯ + e n = n ,   ( e i ≥ 0 , i = 1 , 2 , 3 , …   ) e\_1+e\_2+e\_3+\\cdots +e\_n=n,\\,(e\_i \\ge 0, i= 1, 2, 3,\\dots) e1\+e2\+e3\+⋯\+en=n,(ei≥0,i=1,2,3,…)  
那么对应的母函数就是:  
 g ( x ) = ( 1 + x + x 2 + x 3 + ⋯   ) ( 1 + x 1 + x 2 + ⋯   ) ⋯ ( 1 + x 2 + x 2 + ⋯   ) = ( 1 + x + x 2 + x 3 + ⋯   ) n . g(x) = (1+x+x^2+x^3+\\cdots)(1+x^1+x^2+\\cdots)\\cdots(1+x^2+x^\{2\}+\\cdots) = (1+x+x^2+x^3+\\cdots)^n. g(x)=(1\+x\+x2\+x3\+⋯)(1\+x1\+x2\+⋯)⋯(1\+x2\+x2\+⋯)=(1\+x\+x2\+x3\+⋯)n.

## 代码实现 ##

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 200;
    ll buf[N];
    ll temp[N];
    
    
    void calculate(){
        
        fill(buf, buf + N, 1);
        fill(temp, temp + N, 0);
        for (int k = 2; k < N; ++k){
        
            for (int i = 0; i < N; ++i){
        
                for(int j = 0; i+j < N; j +=k ){
        
                    // temp是当前的k的展开式与上一轮计算的结果.
                    temp[i + j] += buf[i];
                }
            }
            // 更新这一轮的结果.
            memcpy(buf, temp, sizeof(ll)*N);
            fill(temp, temp + N, 0);
        }
    }
    
    int main(int argc, const char** argv) {
        
        calculate();
        int n;
        while (~scanf("%d",&n)){
        
            printf("%lld\n", buf[n]);
        }
        return 0;
    }

下面通过这个表格给出计算 ( 1 + x 1 + x 2 + x 3 + x 4 ) ( 1 + x 2 + x 4 ) (1+x^1+x^2+x^3+x^4)(1+x^2+x^4) (1\+x1\+x2\+x3\+x4)(1\+x2\+x4)的计算过程:  
**(表格A(上一轮计算的结果))**

**(表格B(这一轮计算的结果))**

(整理之后是这一轮计算的值(对应程序中的temp))

(更新这一轮计算的结果准备计算下一轮(对应程序中的buf))

按照上面表格所示的那样,先计算相邻的两项系数作为当前一轮的计算结果,然后在下一轮中座椅一项与下一项进行计算得到下一轮就散的记过,然后更新,这样滚动更新计算,最后的`buf`中的系数就是整数拆分的结果(这里为了便于识别,没有将表格中空白的`0`显示的标出).

## 其它 ##

[format_png]: /images/20230209/9dc94133595c420686f7c77dd218c597.png
[hdu1028]: http://acm.hdu.edu.cn/showproblem.php?pid=1028