2011-10-29 06:52:31Morris
a272. 猥瑣罐頭下樓梯
a272. 猥瑣罐頭下樓梯
/**********************************************************************************/
/* Problem: a272 "猥瑣罐頭下樓梯" from */
/* Language: C (812 Bytes) */
/* Result: AC(0ms, 288KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-10-28 09:20:10 */
/**********************************************************************************/
#include<stdio.h>
typedef struct {
int t[2][2];
}Matrix;
Matrix in, I2, o, init;
Matrix mult(Matrix x, Matrix y) {
Matrix t = o;
int i, j, k;
for(i = 0; i < 2; i++)
for(j = 0; j < 2; j++)
for(k = 0; k < 2; k++) {
t.t[i][k] += x.t[i][j]*y.t[j][k] %10007;
t.t[i][k] %= 10007;
}
return t;
}
void ans(int n) {
Matrix x = init, y = in;
while(n) {
if(n&1) x = mult(x, y);
y = mult(y, y);
n /= 2;
}
printf("%d\n", x.t[0][0]);
}
main() {
int n, a, b;
for(a = 0; a < 2; a++)
for(b = 0; b < 2; b++)
in.t[a][b] = 0, I2.t[a][b] = 0,
o.t[a][b] = 0, init.t[a][b] = 0;
for(a = 0; a < 2; a++) I2.t[a][a] = 1;
init.t[0][0] = 1;
init.t[1][1] = 1;
in.t[0][0] = in.t[0][1] = 1;
in.t[1][0] = 1;
while(scanf("%d", &n) == 1)
ans(n);
return 0;
}
內容 ：
有一天，猥瑣罐頭在下樓梯，不知怎麼了，爬了好久都看不到盡頭.....
圖片來源 : http://znowledge.blogspot.com/2007/11/blog-post_3307.html
罐頭從地下 0 樓開始往下走( 去找猥瑣桑葉? )，他只能一次走 1 或 2 步!
問 : 給你地下共有幾樓，請問罐頭有幾種走法?
輸入說明
：
每一行有一個正整數N ( 1 <= N <= 2147483647 )，代表總共有幾層
輸出說明
：
輸出罐頭有幾種走法!
歐! 對了! 因為答案可能很大， 請把答案 MOD 10007
( MOD 代表取餘數 )
範例輸入 ：
1 2 4
範例輸出 ：
1 2 5
提示
：
如果AC 這題， 可以去挑戰
d639. 企鵝村三兄弟penguin
( 改編自 d639 )
出處
：
/**********************************************************************************/
/* Problem: a272 "猥瑣罐頭下樓梯" from */
/* Language: C (812 Bytes) */
/* Result: AC(0ms, 288KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-10-28 09:20:10 */
/**********************************************************************************/
#include<stdio.h>
typedef struct {
int t[2][2];
}Matrix;
Matrix in, I2, o, init;
Matrix mult(Matrix x, Matrix y) {
Matrix t = o;
int i, j, k;
for(i = 0; i < 2; i++)
for(j = 0; j < 2; j++)
for(k = 0; k < 2; k++) {
t.t[i][k] += x.t[i][j]*y.t[j][k] %10007;
t.t[i][k] %= 10007;
}
return t;
}
void ans(int n) {
Matrix x = init, y = in;
while(n) {
if(n&1) x = mult(x, y);
y = mult(y, y);
n /= 2;
}
printf("%d\n", x.t[0][0]);
}
main() {
int n, a, b;
for(a = 0; a < 2; a++)
for(b = 0; b < 2; b++)
in.t[a][b] = 0, I2.t[a][b] = 0,
o.t[a][b] = 0, init.t[a][b] = 0;
for(a = 0; a < 2; a++) I2.t[a][a] = 1;
init.t[0][0] = 1;
init.t[1][1] = 1;
in.t[0][0] = in.t[0][1] = 1;
in.t[1][0] = 1;
while(scanf("%d", &n) == 1)
ans(n);
return 0;
}
上一篇：a271. 彩色蘿蔔
下一篇：a273. 小朋友下樓梯