#23409: 找到循環區段即可


yes51851823@gmail.com (wseds)

School : 國立花蓮高級工業職業學校
ID : 108813
IP address : [111.243.214.89]
Last Login :
2021-10-01 22:27:22
d639. 企鵝村三兄弟penguin -- jack1 | From: [111.243.226.228] | Post Date : 2020-11-14 16:43

這個數列前三項都是1,第四項開始是前三項的和%10007,因此若忽略前三項就會產生循環區段(2781668)。以0,3,5,9作為數列的開頭即可DP出該循環數列。

如果所詢問n<4,直接輸出1即可。

但若超過3就表示問的是循環數列內的某一項,先將n減掉3(忽略前三項1),只要n超過2781668就取餘,答案就出來了。

 
#23411: Re:找到循環區段即可


yes51851823@gmail.com (wseds)

School : 國立花蓮高級工業職業學校
ID : 108813
IP address : [111.243.214.89]
Last Login :
2021-10-01 22:27:22
d639. 企鵝村三兄弟penguin -- jack1 | From: [111.243.226.228] | Post Date : 2020-11-14 16:46

這個數列前三項都是1,第四項開始是前三項的和%10007,因此若忽略前三項就會產生循環區段(2781668)。以0,3,5,9作為數列的開頭即可DP出該循環數列。

如果所詢問n<4,直接輸出1即可。

但若超過3就表示問的是循環數列內的某一項,先將n減掉3(忽略前三項1),只要n超過2781668就取餘,答案就出來了。


補充:第4項~第2781671項為一次循環的所有內容。

 
#23412: Re:找到循環區段即可


yes51851823@gmail.com (wseds)

School : 國立花蓮高級工業職業學校
ID : 108813
IP address : [111.243.214.89]
Last Login :
2021-10-01 22:27:22
d639. 企鵝村三兄弟penguin -- jack1 | From: [111.243.226.228] | Post Date : 2020-11-14 16:46

這個數列前三項都是1,第四項開始是前三項的和%10007,因此若忽略前三項就會產生循環區段(2781668)。以0,3,5,9作為數列的開頭即可DP出該循環數列。

如果所詢問n<4,直接輸出1即可。

但若超過3就表示問的是循環數列內的某一項,先將n減掉3(忽略前三項1),只要n超過2781668就取餘,答案就出來了。


補充:第4項~第2781671項為一次循環的所有內容。

 
#23414: Re:找到循環區段即可


fdhs109_GT (GT coding)

School : 桃園市私立復旦高級中學
ID : 102099
IP address : [114.32.85.67]
Last Login :
2021-10-25 13:55:49
d639. 企鵝村三兄弟penguin -- jack1 | From: [111.250.209.146] | Post Date : 2020-11-15 00:47

其實本題正解應該是矩陣快速冪,

想法直關,

也很好寫。

循環區段並不是這麼好找,

而且 mod 很大時,

循環區段可能更大,

比賽中也不一定可以即時找到,

還是好好寫矩陣快速冪好了~^^

時間複雜度:$\Theta(k^3\log n)$

 
#24601: Re:找到循環區段即可


weyth (Jane)

School : No School
ID : 136206
IP address : [112.105.121.52]
Last Login :
2021-03-09 10:12:21
d639. 企鵝村三兄弟penguin -- jack1 | From: [112.105.121.52] | Post Date : 2021-03-09 10:22

這個數列前三項都是1,第四項開始是前三項的和%10007,因此若忽略前三項就會產生循環區段(2781668)。以0,3,5,9作為數列的開頭即可DP出該循環數列。

如果所詢問n<4,直接輸出1即可。

但若超過3就表示問的是循環數列內的某一項,先將n減掉3(忽略前三項1),只要n超過2781668就取餘,答案就出來了。


補充:第4項~第2781671項為一次循環的所有內容。


很感謝提供解題方向,另外心得是,整個循環應該是從第二個1 開始,也就是「1,1,3,5...],長度仍為2781668

 
ZeroJudge Forum