【小松鼠和老式计数器】🐿️
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
森林里住着一只叫栗栗的小松鼠，它有个雷打不动的习惯：每天去松树林捡松果，捡回来的数量严格遵循一个规律——
• 第 0 天：刚搬新家，一颗都没有，捡到 0 颗
• 第 1 天：开张啦，捡到 1 颗
• 从第 2 天起：它每天捡到的颗数，恰好是昨天和昨天的昨天捡到的颗数加在一起（它说这是"祖传秘方"） eg:第2天捡到的松果为0+1=1颗
树洞门口挂着一台老式机械计数器，专门显示栗栗当天捡到的松果数。可惜这计数器年纪太大，最多只能数到 1e9（即10^9），再多数一颗就会"咔哒"一声归零重数——也就是说，它显示的数字永远是实际颗数 mod 1e9+1。
栗栗想知道：第 n 天，计数器上会显示几？
Format
Input
一个整数n，0≤n≤10^6
Output
一个整数，表示第n天计数器上显示的数字
Samples
10
55
0
0
1000
989415042
Limitation
1s, 1024KiB for each test case.
第十届西南石油大学程序设计新生赛(正式赛)
- Status
- Done
- Rule
- XCPC
- Problem
- 17
- Start at
- 2026-10-24 14:00
- End at
- 2026-10-24 18:00
- Duration
- 4 hour(s)
- Host
-
AiraKeq
- Partic.
- 50