2011-06-10 20:42:47Morris
d644. 壞脾氣小小皮
http://zerojudge.tw/ShowProblem?problemid=d644
內容 ：
巫師小米是企鵝村首席巫師，也就是法力最強的巫師。
但是小米的召喚獸(每個巫師都有一個各不相同的召喚獸)是一隻海豹，
而且是一隻…脾氣很差的海豹！
因為這隻海豹脾氣很差，和小米的弟弟小皮一樣，
所以小米給這隻海豹取名叫做小小皮。
小小皮每天會跟小米一起練功，
但是小米練功狂太嚴重了……
所以每練一段時間得到的經驗值會因為情緒暴躁而減少。
如果用數列從第一天開始表示小小皮的經驗值會是：
第n天1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9
f(n) 1 , 1 , 2 , 2 , 4 , 6 , 9 , 15 , 24 ...
從第三天開始，經驗值是前兩天相加的和。
但是每逢3x+1(x正整數)的天數(第四天開始)，經驗值-1！
(以上表為例，逢4、7天需要-1)
小米沒日沒夜的練功，
他已經搞不清楚小小皮現在的練得怎麼樣了，
請你寫個程式幫幫他好嗎？
但是小米的召喚獸(每個巫師都有一個各不相同的召喚獸)是一隻海豹，
而且是一隻…脾氣很差的海豹！
因為這隻海豹脾氣很差，和小米的弟弟小皮一樣，
所以小米給這隻海豹取名叫做小小皮。
小小皮每天會跟小米一起練功，
但是小米練功狂太嚴重了……
所以每練一段時間得到的經驗值會因為情緒暴躁而減少。
如果用數列從第一天開始表示小小皮的經驗值會是：
第n天1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9
f(n) 1 , 1 , 2 , 2 , 4 , 6 , 9 , 15 , 24 ...
從第三天開始，經驗值是前兩天相加的和。
但是每逢3x+1(x正整數)的天數(第四天開始)，經驗值-1！
(以上表為例，逢4、7天需要-1)
小米沒日沒夜的練功，
他已經搞不清楚小小皮現在的練得怎麼樣了，
請你寫個程式幫幫他好嗎？
輸入說明
：
每個測資點僅一筆測資，不需EOF結束。
每個測資只有一個正整數n(1<=n<=2147483647)，代表要求的天數。
每個測資只有一個正整數n(1<=n<=2147483647)，代表要求的天數。
輸出說明
：
對於第n天小小皮的經驗值，請輸出其mod100019的值
範例輸入 ：
10
範例輸出 ：
38
提示
：
共計三個測資點，配分30％、35％、35％
出處
：
jack1
(管理：jack1)
作法描述 by (leopan0922)
經過觀察
答案會是fib(n)-fib(n-1)/2;
測資到int_max
所以又要用D&C
/**********************************************************************************/
/* Problem: d644 "壞脾氣小小皮" from jack1 */
/* Language: C */
/* Result: AC (4ms, 264KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-06 09:06:13 */
/**********************************************************************************/
#include<stdio.h>
typedef struct {
long long 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] %100019;
t.t[i][k] %= 100019;
}
return t;
}
long long ans(int n) {
Matrix x = I2, y = init;
while(n) {
if(n&1) x = mult(x, y);
y = mult(y, y);
n /= 2;
}
return x.t[1][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] = init.t[0][1] = 1;
init.t[1][0] = 1;
while(scanf("%d", &n) == 1) {
printf("%d\n", (ans(n) - ans(n-1)/2 + 100019)%100019);
}
return 0;
}
上一篇：d643. 勞動的符咒
下一篇：d645. 輪下亡魂