yes51851823@gmail.com
(wseds)
學校
:
國立花蓮高級工業職業學校
編號 : 108813
來源 : [114.36.212.168]
最後登入時間 ：
2024-10-17 21:35:26
這個數列前三項都是1，第四項開始是前三項的和%10007，因此若忽略前三項就會產生循環區段（2781668）。以0,3,5,9作為數列的開頭即可DP出該循環數列。
如果所詢問n<4，直接輸出1即可。
但若超過3就表示問的是循環數列內的某一項，先將n減掉3（忽略前三項1），只要n超過2781668就取餘，答案就出來了。
yes51851823@gmail.com
(wseds)
學校
:
國立花蓮高級工業職業學校
編號 : 108813
來源 : [114.36.212.168]
最後登入時間 ：
2024-10-17 21:35:26
這個數列前三項都是1，第四項開始是前三項的和%10007，因此若忽略前三項就會產生循環區段（2781668）。以0,3,5,9作為數列的開頭即可DP出該循環數列。
如果所詢問n<4，直接輸出1即可。
但若超過3就表示問的是循環數列內的某一項，先將n減掉3（忽略前三項1），只要n超過2781668就取餘，答案就出來了。
補充：第4項～第2781671項為一次循環的所有內容。
yes51851823@gmail.com
(wseds)
學校
:
國立花蓮高級工業職業學校
編號 : 108813
來源 : [114.36.212.168]
最後登入時間 ：
2024-10-17 21:35:26
這個數列前三項都是1，第四項開始是前三項的和%10007，因此若忽略前三項就會產生循環區段（2781668）。以0,3,5,9作為數列的開頭即可DP出該循環數列。
如果所詢問n<4，直接輸出1即可。
但若超過3就表示問的是循環數列內的某一項，先將n減掉3（忽略前三項1），只要n超過2781668就取餘，答案就出來了。
補充：第4項～第2781671項為一次循環的所有內容。
fdhs109_GT
(GT coding)
學校
:
桃園市私立復旦高級中學
編號 : 102099
來源 : [140.114.123.88]
最後登入時間 ：
2024-09-05 18:00:19
其實本題正解應該是矩陣快速冪，
想法直關，
也很好寫。
循環區段並不是這麼好找，
而且 mod 很大時，
循環區段可能更大，
比賽中也不一定可以即時找到，
還是好好寫矩陣快速冪好了～^^
時間複雜度：$\Theta(k^3\log n)$
這個數列前三項都是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