UOJ Logo Universal Online Judge

UOJ

#500. 任意基DFT

统计

给定 $n$ 次多项式

\begin{equation} f(x) = \sum_{i=0}^{n} a_ix^i \end{equation}

$Q$ 次询问,第 $i$ 次询问 $f(q_i)$ 对 $998244353$ 取模的值。

输入格式

由于本题的数据范围较大,所有测试点的 $q_i$ 将在程序内生成。

第一行两个整数 $n,Q$。$n,Q$ 的意义见题目描述。

第二行 $n+1$ 个整数,第 $i$ 个整数表示 $a_{i-1}$

第三行三个整数 $q_0,q_{\mathrm{x}},q_{\mathrm{y}}$,表示 $q_i$ 的生成方式。

$q_i$ 按照如下规则生成:

$\forall 1 \leq i \leq Q,q_i=(q_{i-1} \times q_{\mathrm{x}}+q_{\mathrm{y}})\bmod 998244353$

输出格式

由于输出规模过大,你只需要输出所有询问答案取完模之后的 $\mathbin{\mathrm{xor}}$ 和即可。

样例一

input

2 2
1 2 3
1 2 1

output

128

explanation

$q_1=2 \times q_0 +1=3$

$q_2=2 \times q_1 +1=7$

答案 $=(1+2 \times 3+ 3 \times 3^2) \mathbin{\mathrm{xor}} (1+2 \times 7+3 \times 7^2)=34 \mathbin{\mathrm{xor}} 162=128$

样例二

见样例数据下载

数据范围

测试包编号$n\leq $$Q \leq$$特殊性质 $分值
$1$$1000$$1000$$5$
$2$$10^5$$10^5$$15$
$3$$2.5 \times 10^5$$2.5 \times 10^5$$15$
$4$$5 \times 10^5$$q_{\mathrm{y}}=0$$25$
$5$$25$
$6$$10^6$$15$

对于所有测试数据,满足 $1 \leq n \leq 2.5 \times 10^5, 1 \leq Q \leq 10^6, 2 \leq q_{\mathrm{x}} < 998244353, 0 \leq q_0,q_{\mathrm{y}} < 998244353$。

时间限制:$\texttt{1s}$

空间限制:$\texttt{512MB}$

下载

样例数据下载