G - ★★糖果魔法阵★★
时间限制: 2000ms
空间限制: 256MB
题目描述
Gemma 是一名女巫,她擅长使用各种各样的魔法。似乎大部分女巫都喜欢糖果,当然,Gemma 也不例外。
每天,Gemma都会用她的魔力催动若干次糖果魔法阵,从而得到吃不完的糖果。
具体来说,每次用魔力催动糖果魔法阵获得的糖果数与放入魔法阵中的糖果数有关。假设放入魔法阵中的糖果数为 $x (x \gt 0)$,那么用魔力催动一次魔法阵后获得的糖果数为 $\displaystyle \frac{x^{4}+12x^{2}+4}{4x(x^{2}+2)} \bmod 9982443534$(原先放入的 x 颗糖果已经作为催动魔法阵的代价永远消失了)。
特别地,如果 $x=0$,那么便意味着此次催动魔法阵获得的糖果数也为 $0$。
为了得到尽可能多的糖果,$Gemma$ 每次都会把她当前所有的糖果放入魔法阵。尽管有些时候这种做法并不是最优的,但谁让这个女巫傻乎乎的呢。
另外,$Gemma$ 的魔力是有限的,每次催动魔法阵都会消耗她一定的魔力,并且,她必须在每晚通过睡“魔法觉”来恢复她的魔力。
具体来说,假设从第一天开始到第$ m$ 天结束时她总共催动了 k 次魔法阵,且此时拥有的糖果数量为 $x$,那么在“魔法觉”之后,第 $m+1$ 天她的魔力会恢复为 $(116195172^{4^{k}}-882049183^{4^{k}})mx \bmod 998244353$。在任何时刻,魔力都不会为负,并且睡“魔法觉”不会消耗任何糖果。
$Gemma$ 为了糖果不停地努力,只要当天还有足够的魔力,她就会一直催动魔法阵,直到剩余魔力不足以再催动一次魔法阵,她才会去睡她的“魔法觉”。
现在 $Gemma$ 想知道,经过她的不懈努力,在第 $n$ 天结束时,她会拥有多少颗糖果。在一开始,她只有 $1$ 颗糖果。
输入描述:
第一行一个整数 $s,c,q (1 \leq s,c \leq 10^{9},1 \leq q \leq 1000)$,分别表示初始魔力,每次催动魔法阵消耗的魔力和询问次数;
接下来 $q$ 行,第$i (1 \leq i \leq q)$ 行一个整数 $n_{i} (1 \leq n_{i} \leq 2 \times 10^{7})$,表示询问第 $n_{i}$ 天结束时拥有的糖果数。
对于全部询问,保证 $\sum n \leq 2 \times10^{7}$。
输出描述:
对于每次询问,输出一行一个整数表示答案。
输入
10 6 2
1
10
输出
915057325
678018512
说明
在第一次询问中,第一天会催动一次魔法阵,第一天结束时拥有 $\displaystyle \frac{17}{12} \bmod 998244353=915057325$ 颗糖果。
在第二次询问中,第 $10$ 天结束时拥有 $678018512$ 颗糖果。