分数: 675 点
问题陈述
定义一个序列 a_1, a_2, a_3, \dots 如下:
a_n = \begin{cases} x & (n=1) \\ y & (n=2) \\ a_{n-1} + a_{n-2} & (n \geq 3) \\ \end{cases}
查找 每对 \left( \displaystyle \prod_{i=1}^N a_i \right) \bmod{998244353}.
你被给予 T 测试用例解决。
约束
- 1 \leq T \leq 5
- 1 \leq N \leq 10^{18}
- 0 \leq x \leq 998244352
- 0 \leq y \leq 998244352
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出。在这里, \mathrm{case}_i 表示 i- 第一个测试用例。 总共
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
每个测试用例均按以下格式给出:
N x y
输出
打印 T 行。的 i- 第行应包含以下问题的答案 i- 第一个测试用例。 总共
示例输入 1
3 5 1 1 2024 11 22 1000000000000000000 12345 6789
示例输出 1
30 577322229 726998219
对于第一个测试用例,序列的元素是 1, 1, 2, 3, 5, 8, \dots。因此,答案是 (1 \times 1 \times 2 \times 3 \times 5) \bmod{998244353} = 30.