posts - 99, comments - 8, trackbacks - 0

//本來以為是一道簡單題誰知道。。。。
//用遞歸寫想都不要想，絕對超時，所以還應(yīng)當(dāng)回到題目本身的分析上來
//正確思路是：因為mod7的關(guān)系，而且f(1)=f(2)=1，所以f(n)的值是循環(huán)分布的，而且一定會回到f(n-1)=f(n)=1，
//并且還可得出，這個循環(huán)不大于49，因為相鄰連個f只有7種取值，這樣f(n-1)和f(n)共有49種組合。
//所以，只要找出循環(huán)因子即可，尋找方法正是根據(jù)f(n-1)=f(n)再次出現(xiàn)的地方來計算
//可以首先為這個題目寫一個測試的程序設(shè)定一個 a b n（n 比較小時）的值看看輸出規(guī)律

1

#include <stdio.h>
2

#include <stdlib.h>
3

int f[51];
4

int main ()
5

{
6

int a, b, n;
7

while ( scanf ("%d %d %d", &a , &b, &n) != EOF && a != 0 && b != 0 && n != 0 )
8

{
9

f[1] = f[2] = 1;
10

int i;
11

for (i = 3; i < 51; i ++)
12

{
13

f[i] = (a * f[i - 1] + b * f[i - 2]) % 7;
14

if ( f[i] == 1 && f[i - 1] == 1 ) //找到循環(huán)因子 i
15

{
16

break;
17

}
18

}
19

20

n = n % (i - 2);
21

if (n == 0) //剛好經(jīng)過一個循環(huán)
22

printf ("%d\n", f[i - 2]); //開始時，我是因為看了測試程序，把這里設(shè)定為輸出 0 這種想法是錯的，太片面了，因為數(shù)據(jù)范圍很大
23

else
24

printf ("%d\n", f[n]);
25

}
26

//system ("pause");
27

return 0;
28

}
29

30

posted on 2010-08-24 14:01 雪黛依夢閱讀(1486) 評論(1) 編輯收藏引用所屬分類: 簡單題、技巧題

FeedBack:

# re: hdu 1005

2011-10-20 14:56 | WonderMan

遞歸想都不要想？矩陣乘法+快速冪不高興回復(fù) 更多評論

刷新評論列表

只有注冊用戶登錄后才能發(fā)表評論。
【推薦】100%開源！大型工業(yè)跨平臺軟件C++源碼提供，建模，組態(tài)！

相關(guān)文章: HDU 1061 HDU 1058 HDU 1056 hdu 1048 hdu 1040 hdu 1021 HDU 1017 HDU 1014 HDU 1012 HDU 1008

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理