2011-06-10 20:36:37Morris
d639. 企鵝村三兄弟penguin
內容 ：
企鵝村村長裡諾有三個兒子
大哥小米企鵝，企鵝村首席巫師，擅長黑暗魔法、冰魔法
二哥小波企鵝，祭司，擅長神聖魔法
三弟小皮企鵝，魔弓手，擅長製作附有魔法的箭
由於在練功狂大哥小米企鵝的督促之下，
小波企鵝和小皮企鵝無奈的只好一起練功。
三隻企鵝每天的經驗值，如果排成一條數列的話，
剛好會像是這樣：
1 1 1 , 3 5 9 , 17...
前三個數字是第一天小皮、小波、小米的經驗值
中間三個數字是第二天三企鵝的經驗值
以此類推
這條數列的規則就是，從第四項開始的值，都是前三項的和…
大哥小米企鵝，企鵝村首席巫師，擅長黑暗魔法、冰魔法
二哥小波企鵝，祭司，擅長神聖魔法
三弟小皮企鵝，魔弓手，擅長製作附有魔法的箭
由於在練功狂大哥小米企鵝的督促之下，
小波企鵝和小皮企鵝無奈的只好一起練功。
三隻企鵝每天的經驗值，如果排成一條數列的話，
剛好會像是這樣：
1 1 1 , 3 5 9 , 17...
前三個數字是第一天小皮、小波、小米的經驗值
中間三個數字是第二天三企鵝的經驗值
以此類推
這條數列的規則就是，從第四項開始的值，都是前三項的和…
輸入說明
：
每個測資點僅一個整數n，1<=n<=2147483647
輸出說明
：
請輸出第n項的值。(請視第一項、第二項、第三項為1，無第0項)
由於數字可能很大，請將結果mod10007後輸出
由於數字可能很大，請將結果mod10007後輸出
範例輸入 ：
8
範例輸出 ：
31
提示
：
1.拜託不要這麼快破台嘛…
2.共三個測資點30%、35%、35%，
第一個測資點即範例測資。
出處
：
/* Problem: d639 "企鵝村三兄弟penguin" from jack1 */
/* Language: C */
/* Result: AC (1ms, 262KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-05 20:37:58 */
/**********************************************************************************/
#include<stdio.h>
typedef struct {
int t[3][3];
}Matrix;
Matrix in, I3, o, init;
Matrix mult(Matrix x, Matrix y) {
Matrix t = o;
int i, j, k;
for(i = 0; i < 3; i++)
for(j = 0; j < 3; j++)
for(k = 0; k < 3; 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 < 3; a++)
for(b = 0; b < 3; b++)
in.t[a][b] = 0, I3.t[a][b] = 0,
o.t[a][b] = 0, init.t[a][b] = 0;
for(a = 0; a < 3; a++) I3.t[a][a] = 1;
init.t[0][0] = 5;
init.t[1][0] = init.t[0][1] = 3;
init.t[0][2] = init.t[1][1] = init.t[1][2] = 1;
init.t[2][0] = init.t[2][1] = init.t[2][2] = 1;
in.t[0][0] = in.t[0][1] = 1;
in.t[1][0] = in.t[1][2] = 1;
in.t[2][0] = 1;
while(scanf("%d", &n) == 1) {
if(n <= 3) puts("1");
else if(n == 4) puts("3");
else ans(n-5);
}
return 0;
}
上一篇：d910. 數學達人2
下一篇：d643. 勞動的符咒
(悄悄話)
2012-04-21 14:09:34