题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=1028

题目描述

“Well, it seems the first problem is too easy. I will let you know how foolish you are later.” feng5166 says.

“The second problem is, given an positive integer N, we define an equation like this:
$$ N=a[1]+a[2]+a[3]+...+a[m]; a[i]>0,1<=m<=n; $$="" <="" p="">

My question is how many different equations you can find for a given N.

For example, assume N is 4, we can find:
$$ 4 = 4; 4 = 3 + 1; 4 = 2 + 2; 4 = 2 + 1 + 1; 4 = 1 + 1 + 1 + 1; $$

so the result is 5 when N is 4. Note that “4 = 3 + 1” and “4 = 1 + 3” is the same in this problem. Now, you do it!”

思路

搞到母函数了,这题的母函数是$G(x) = (1+x+x^2+x^3+\cdots+x^N)(1+x^2+x^4+\cdots+x^N)\cdots (1+x^N)$,x表示数字,x的指数表示数字的组合,由于每个数字使用次数不限,$(1+x+x^2+x^3+\cdots+x^N)$表示单独的数字1可组成的数字有$0,1,2,3,4\cdots,(1+x^2+x^4+\cdots+x^N)$表示单独的数字2可组成的数字有$0,2,4,6, \cdots$,以此类推,这里每一个表达式(即一个括号的表达式)的1表示0个数字的组合,即$1*x^0$。

在详细说一下每个表达式怎么来的,比如单独的数字5可组成那些数?0(0个5),5(1个5),10(2个5)…表达式即($1*x^{0*5}+1*x^{1*5}+1*x^{2*5}+\cdots=(1+x^5+x^{10}+\cdots)$,每一项的系数表示情况数(例如以5拆分数字10的情况只有一种5+5)。

那么把母函数展开后,$x^N$的系数即表示N的拆分数(整数拆分成若干整数的和,办法不一,不同拆分法的总数叫做拆分数。)

展开思路就是,将第二个表达式与第一个展开得一个表达式,然后将第三个与前两个表达式展开,以此类推。

比如$(1+x)(1+x^2)(1+x^3)=(1+x+x^2+x^3)(1+x^3)$,然后继续展开。

至于怎么展开,看代码注解,这里第一个表达式是最前面那个表达式,后一个表达式是紧接着第一个表达式。

AC代码

/*************************************************************************
    > File Name: 1028.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-06-29 Mon 23:04:06 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;
const int _max = 125;

int main()
{
#ifdef Oj
    // freopen(".in", "r", stdin);
#endif
    // G(x) = (1+x+x^2+x^3+...+x^N)(1+x^2+x^4+...+x^N)...(1+x^N) 母函数
    int c1[_max], c2[_max]; // c1表示每一项的的系数,c2表示每个表达式的临时系数
    int N;
    while(cin >> N && N) {
        for(int i=0; i<=N; ++i) {
            c1[i] = 1; // 每一项应该初始化为1,即1+x+x^2+...+x^N
            c2[i] = 0;
        }
        for(int i=2; i<=N; ++i) { // 从第二个表达式开始展开,
            for(int j=0; j<=N; ++j) // 表示第一个表达式的第j项
                for(int k=0; k+j<=N; k+=i) // k表示后一个表达式的第k项
                    c2[k+j] += c1[j]; // 这里应该是相当于C1*x^j * x^k=C1*x^(j+k),即c2[k+j]+=C1[j]
                for(int j=0;j<=N; ++j) {
                    c1[j] = c2[j]; // 确定x^j的系数
                    c2[j] = 0; // 中间变量归零
                }
        }
        printf("%d\n", c1[N]); // x^N的系数即拆分数。
    }
    return 0;
}