2011-06-01 22:03:29Morris
d828. Pascal's triangle's secret (II)
http://zerojudge.tw/ShowProblem?problemid=d828
內容 ：
帕斯卡三角形 (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 後輸出。
定義此三角形的頂端(第 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 後輸出。
輸入說明
：
多個整數 n (0 <= n <= 2147483647)。
輸出說明
：
對於每個整數 n ，輸出一個正確解答。
範例輸入
：
0 1
範例輸出 ：
1 1
提示
：
Divide and Conquer
出處
：
/**********************************************************************************/
/* Problem: d828 "Pascal's triangle's secret (II)" from */
/* Language: C */
/* Result: AC (216ms, 264KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-01 21:12:19 */
/**********************************************************************************/
#include<stdio.h>
void Mod(int *N) {
if(*N > 50000) (*N)%=10000;
}
main() {
int N;
while(scanf("%d", &N) == 1) {
if(N < 2) puts("1");
else {
int a=1, b=1, c=1, d=0;
int A=1, B=0, C=0, D=1, t1, t2, t3, t4;
while(N) {
if(N&1) {
t1 = A*a + B*c;
t2 = A*b + B*d;
t3 = C*a + D*c;
t4 = C*b + D*d;
A = t1, B = t2, C = t3, D = t4;
Mod(&A), Mod(&B), Mod(&C), Mod(&D);
}
N /= 2;
t1 = a*a + b*c;
t2 = a*b + b*d;
t3 = a*c + c*d;
t4 = b*c + d*d;
a = t1, b = t2, c = t3, d = t4;
Mod(&a), Mod(&b), Mod(&c), Mod(&d);
}
printf("%d\n", A%10000);
}
}
return 0;
}
/*a b
c d*/
上一篇：d624. 燈泡問題