ลำดับคำฟีโบนัชชีซึ่งประกอบด้วยสตริงบิตนิยามดังนี้:
$$ F(n)=\begin{cases} 0 & n=0,\\ 1 & n=1,\\ F(n-1)+F(n-2) & n\ge 2. \end{cases} $$
ในที่นี้ $+$ หมายถึงการต่อสตริง สมาชิกตัวแรก ๆ มีดังนี้:
| $n$ | $F(n)$ |
|---|---|
| $0$ | $0$ |
| $1$ | $1$ |
| $2$ | $10$ |
| $3$ | $101$ |
| $4$ | $10110$ |
| $5$ | $10110101$ |
| $6$ | $1011010110110$ |
| $7$ | $101101011011010110101$ |
| $8$ | $1011010110110101101011011010110110$ |
| $9$ | $1011010110110101101011011010110110101101011011010110101$ |
เมื่อกำหนดรูปแบบบิต $p$ และจำนวน $n$ ให้ จงหาว่า $p$ ปรากฏใน $F(n)$ กี่ครั้ง
ข้อมูลนำเข้า
บรรทัดแรกของแต่ละกรณีทดสอบประกอบด้วยจำนวนเต็ม $n$ ($0 \le n \le 100$) บรรทัดที่สองประกอบด้วยรูปแบบบิต $p$ โดย $p$ ไม่เป็นสตริงว่างและมีความยาวไม่เกิน $100\,000$ อักขระ
ข้อมูลส่งออก
สำหรับแต่ละกรณีทดสอบ ให้แสดงหมายเลขกรณีทดสอบตามด้วยจำนวนครั้งที่รูปแบบบิต $p$ ปรากฏใน $F(n)$ การปรากฏแต่ละครั้งอาจทับซ้อนกันได้ จำนวนครั้งที่ปรากฏจะน้อยกว่า $2^{63}$
ตัวอย่าง
ข้อมูลนำเข้า 1
6 10 7 10 6 01 6 101 96 10110101101101
ข้อมูลส่งออก 1
Case 1: 5 Case 2: 8 Case 3: 4 Case 4: 4 Case 5: 7540113804746346428