P17802 [CXOI2026] 想要变成鹰的鱼
题目背景
本题时间限制约为 std 的 $1.5\sim 2$ 倍，可能会有点卡常，请精细实现您的代码。
题目描述
定义 Fibonacci 序列 $f_n$ 满足 $f_1=f_2=1,f_i=f_{i-1}+f_{i-2}(i\ge 3)$。
现在给定一个长度为 $n$ 的序列 $a_1,a_2,\ldots,a_n$，你需要对每个 $i=1,2,3,\ldots,n$ 都求出 $\operatorname{lcm}(f_{a_1},f_{a_2},\ldots,f_{a_i})\bmod 998244353$ 的值。
输入格式
第一行一个整数 $n$。
然后一行 $ n$ 个整数 $a_1,a_2,\ldots,a_n$。
输出格式
一行 $n$ 个整数分别表示 $i=1,2,3,\ldots,n$ 时的答案。
说明/提示
**本题采用捆绑测试。**
对于 $15\%$ 的分数满足 $n\le 1000$。
对于另外 $20\%$ 的分数满足 $a_i\le 10^6$。
对于另外 $25\%$ 的分数满足 $a_i$ 在 $[1,10^9]$ 范围内等概率均匀随机生成。
对于全部的分数满足 $1\le n\le 10^5,1\le a_i\le 10^9$。