c188: 拉瑪努金的逆襲

內容

在電影「天才無限家」(The Man Who Knew Infinity)裡，拉瑪努金到了劍橋拜入 Hardy(哈代)門下。師徒倆一個充滿創意與洞察，一個善於嚴謹驗證。兩個人合作無間，創造了許多突破性的進展。但，學術圈同儕並不太認同他的研究。

Hardy 為了找到更多人支持他，帶著拉馬努金找了劍橋組合學大師 MacMahon 挑戰組合數學。

問題如下：一個整數可以由另一些整數的和來表示。比如 4

4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

總共可以找到 5 種方式來表達。計為 P(4) = 5

他們找了 MacMahon 挑戰 P(200) ，當兩人到約定時間，同時翻開手底答案時， MacMahon 大為震驚。從此對拉馬努金從原本不屑一顧，轉而大力支持他成為劍橋研究員。

問題來了，你還記得 P(200) 是多少嗎？在當年只能手算的年代裡，能算到 P(200)已經是大師級了，時至今日，電腦可以幫助我們大量運算，快速的得到答案。

所以請你用程式計算出來吧。

輸入

輸入有多行，每一行有一個正整數 n (n <= 200)，代表待組合的數。

0
1
200

輸出

請輸出共可以有多少種方法可以組合出這個數。也就是 P(n)

1
1
3972999029388

解題思路

先把前幾項列出來

P(1) = 1
P(2) = 1+1, 2
P(3) = 1+1+1, 2+1, 3
P(4) = 1*4, 2+1+1, 2+2, 3+1, 4
P(5) = 1*5, 2+1+1+1, 2+2+1, 3+1+1, 3+2, 4+1, 5
P(6) = 1*6, 2+1+1+1+1, 2+2+1+1, 2+2+2, 3+1+1+1, 3+2+1, 3+3, 4+1+1, 4+2, 5+1, 6

不要看開頭和結尾(全部都是 1 和自己本身)觀察上面規律會發現

P(3) 2 + P(1)的那一項
P(4) 2 + P(2)的那兩項，3 + P(1)的那一項
P(5) 2 + P(3)的那三項，3 + P(2)的那兩項，4+P(1)的那一項。
…

之後同理類推，就可以列出下表

其中 P(1) 和 P(2) 是特例，
P(1) 的所有 1 相加和自己本身相同，所以要-1
P(2) 則是因為他的全部都是 1 和 1 + P(1) 重疊到了，所以也要-1

得到規律後按照規律建成表之後查表輸出答案即可。

完整程式碼

AC (2ms, 80KB)

#include <stdio.h>
#define MAX 201

int main()
{
    unsigned long long int list[MAX] = { 1 };
    int n;
    for (int i = 1; i < MAX; i++)
    {
        for (int j = i; j < MAX; j++)
            list[j] += list[j - i];
    }
    while (scanf(" %d", &n) == 1)
    {
        printf("%llu\n", list[n]);
    }
    return 0;
}