a344. TOI 2020/11 潛力組：包雞紙包

題目描述

本題官方完整題名為「包雞紙包雞包紙包雞」。定義費式數列 F_0=1、F_1=1，其後每項為前兩項之和。包雞數列按原題公式定義為：

T_n = F_(F_0) + F_(F_1) + ⋯ + F_(F_n)。

例如原題列出 T_0=F_1、T_1=F_1+F_1、T_2=F_1+F_1+F_2，以及 T_5=F_1+F_1+F_2+F_3+F_5+F_8。請計算第 n 項對指定整數取餘數的結果。

輸入格式

輸入一個整數 n，官方輸入格式列出的範圍為 0 ≤ n ≤ 10^8。

輸出格式

輸出 T_n 除以 1080494663 的餘數。

原題分組限制

原題分組文字寫為：25 分，1 ≤ N ≤ 10000；75 分，1 ≤ N ≤ 10^7。此處保留原文的 N 與上下界，未擅自統一為主輸入限制。

範例 1

輸入：

1

輸出：

1

範例 2

輸入：

2

輸出：

4

範例 3

輸入：

5

輸出：

49

原題疑義與審核備註

官方原題存在實質矛盾：公式與 F_0=F_1=1 定義推出 T_1=2，但官方範例 1 為輸入 1、輸出 1。範例照錄，不將 1 修改成 2，也不據此擅改公式。

主輸入上限 10^8 與分組上限 10^7 不一致。這兩項問題未釐清前，本題只能保留為待審資料，不能宣稱可建立正確評測。

來源

TOI 2020 年 11 月練習賽潛力組，依官方 PDF 整理。

官方原題：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202011/Wrapper.pdf

標籤：TOI 歷屆