d828: Pascal's triangle's secret (II)
Tags :
Accepted rate : 232人/277人 ( 84% ) [非即時]
評分方式:
Tolerant

最近更新 : 2010-11-02 12:24

Content
帕斯卡三角形 (Pascal's Triangle) 是一個特別的三角數列,已經發現許多的數學性質可以和它有所關連。

定義此三角形的頂端(第 0 列)為1,之後的每一列都比上一列多一個數字,因此第 n 列的總共有 n + 1 個數字,每一列以等腰三角形的形式置中對齊。
除了第 0 列的任一個數字都是左上和右上數字的和,如果這個數字是在這一列的最左或最右側,它的左上及右上將沒有數字,此時我們將沒有數字的地方視為 0 。

綜合以上性質,可以得到以下的三角形,在此只列出到第四列:

第 0 列:    1
第 1 列:   1 1
第 2 列:  1 2 1
第 3 列: 1 3 3 1
第 4 列:1 4 6 4 1

不過本題為了方便敘述起見,我們將帕斯卡三角形稍微變形一下,原本置中對齊變成了靠左對齊,就像這樣:

第 0 列:1
第 1 列:1 1
第 2 列:1 2 1
第 3 列:1 3 3 1
第 4 列:1 4 6 4 1

這次要問你的是,從第 n 列的第一個數字開始往右上角相加,直到沒有數字為止,此時的總和為多少?
(更白話地說,若定義每一列的第一個數字為第 0 項,且三角形外空白部分全部補 0 ,則對於每一個 i (0 <= i <= n) ,將每個第 n - i 列的第 i 項  相加的總和為何?)
答案可能非常大,請 Mod 10000 後輸出。
Input
多個整數 n (0 <= n <= 2147483647)。
Output
對於每個整數 n ,輸出一個正確解答。
Sample Input #1
0
1
Sample Output #1
1
1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 10.0s , <1M
Hint :
Divide and Conquer
Tags:
出處:
[管理者: as89366(你為什麼不問問神奇海螺呢?) ]


ID User Problem Subject Hit Post Date
16623 freedom50199...(帥氣魔方生) d828
觀念
1046 2019-01-22 23:12