#P12273. [蓝桥杯 2024 国 Python B] 异位和

[蓝桥杯 2024 国 Python B] 异位和

题目描述

给定一个数组 AA,我们称 AA 的异位和数组为另一个等长的数组 B=F(A)B = F(A),满足

Bi=jiAjB_i = \sum_{j \neq i} A_j

类似地,其二次异位和数组为 F(F(A))F(F(A)),三次异位和数组为 F(F(F(A)))F(F(F(A))),以此类推。

给定若干次询问,每次问 AAkik_i 次异位和数组的第 xix_i 个元素的值是多少。输出答案对 998244353998244353 取模后的结果。

输入格式

输入的第一行包含一个整数 nn

第二行包含 nn 个整数 A1,A2,,AnA_1, A_2, \ldots, A_n,相邻整数之间使用一个空格分隔。

第三行包含一个整数 QQ 表示询问次数。

接下来 QQ 行,每行包含两个整数 ki,xik_i, x_i 表示一组询问,用一个空格分隔。

输出格式

输出 QQ 行,每行包含一个整数,依次表示每个询问的答案。

5
1 2 3 4 5
4
1 1
2 5
7 3
999 4
14
50
49152
781284616

提示

评测用例规模与约定

  • 对于 60%60\% 的评测用例,1n,Q,ki50001 \leq n, Q, k_i \leq 5000
  • 对于所有评测用例,1n,Q1051 \leq n, Q \leq 10^51Ai,ki1091 \leq A_i, k_i \leq 10^91xin1 \leq x_i \leq n