Problem 10497 Sweet Child Makes Trouble，麻煩的小孩

通常可愛的小孩會製造一些麻煩，例如說拿別人的東西總是不會歸回原位放好，如果拿了 3 個人的東西，而不歸回原位放好的擺法有 2 個，2 3 1 和 3 1 2。所以給你一個 n 值就是小孩拿了 n 樣東西，要你求出不歸回原位的擺法有幾種。

此處要用到大數概念，最長位數有 1976 位這麼長，所以處理起來頗為耗時，不過也只需處理一次並且記錄在字元陣列內，最後用 puts() 印出即可：

#define SIZE 800
#define LEN 2000
int p[SIZE + 1][LEN + 1] = {0};
char output[SIZE + 1][LEN + 1];
void create()
{
    int i; 
    p[0][0] = 1;
    p[1][0] = 0;
    output[0][0] = '1';
    output[0][1] = '\0';
    output[1][0] = '0';
    output[1][1] = '\0';
    int j, k, s, count = 0;
    for (i = 2; i <= SIZE; i ++)
    {
        for (j = 0; j <= LEN; j ++)
        {
            p[i][j] += (p[i - 1][j] + p[i - 2][j]) * (i - 1);
            p[i][j + 1] += p[i][j] / 10, p[i][j] %= 10;
        }
        
        for (j = LEN; j >= 0; j --)
            if (p[i][j] > 0) break;
        for (k = j, s = 0; k >= 0; k --, s ++)
            output[i][s] = p[i][k] + '0';
        output[i][s] = '\0'; 
    }
}

int main()
{
    int n;
    create();
    while (scanf("%d", &n) == 1 && n != -1)
        puts(output[n]);
    return 0;
}

By David.K

p10497題目連結
回ACM題庫目錄
回首頁