三月 27, 2020 · OI 题解
「UOJ500」任意基DFT
给定 $n$ 次多项式 $\displaystyle{ f(x) = \sum_{i=0}^n a_i x^i }$ $Q$ 次询问，第 $i$ 次询问 $f(q_i)$ 对 $998244353$ 取模的值。 其中 $q_i$ 是一个一阶线性递推，给定 $q_0, x, y$ ，满足 $\displaystyle{ q_n = x q_{n-1} + y }$ $1 \leq n \leq 2.5 \times 10^5, \ 1 \leq Q \leq 10^6, \ 2 \leq x < 998244353, \ 0 \leq q_0, y < 998244353$ 。