hdu 1028 Ignatius and the Princess III

Problem

acm.split.hdu.edu.cn/showproblem.php?pid=1028

Reference

母函数（Generating function）详解 — TankyWoo
ACM 母函数专题

Meaning

将一个正整数 n 拆成若干个正整数的和，问有多少种拆分方法。

Analysis

相当于有 n 个无差别的球，放到 n 个无差别的盒里，允许空盒，也允许一个盒放多个球，问多少种放法。
一个组合数学的问题吧，母函数这个东西不知道怎么就把加法和幂的乘积对应起来了…很神奇（没有这方面基础…）。只是学习一下拆数的模版。

Code

#include <cstdio>
using namespace std;
const int N = 120;

int c[N+1]; // c[i]：i 的拆数方案数（拆分数）
int tmp[N+1];

void table()
{
    for(int i = 0; i <= N; ++i)
    {
        c[i] = 1;
        tmp[i] = 0;
    }
    for(int exp = 2; exp <= N; ++exp)
    {
        for(int i = 0; i <= N; ++i)
            for(int j = 0; j <= N - i; j += exp)
                tmp[i+j] += c[i];
        for(int i = 0; i <= N; ++i)
        {
            c[i] = tmp[i];
            tmp[i] = 0;
        }
    }
}

int main()
{
    table();
    for(int n; scanf("%d", &n) != EOF; )
        printf("%d\n", c[n]);
    return 0;
}