多项式(polynomial)
题目大意:
给出一个 n 次多项式
\(f(x)=\sum_{i=0}^na_ix^i\)
对于\(k ≤ x ≤ k + l − 1\) 的\(l\) 个\(x\),分别求出\(f(x)\) 的值。由于答案可能会很大,你只需:输出\(f(x) \space mod \space 10^m\)的结果。
第一行共四个整数\(n, k, l,m\),中间用一个空格隔开,含义如题意所述。接下来\(n+1\)行,每行一个整数,依次给出了\(an, an−1, . . . , a0\)。
- 【算法要点】
- 高精度运算差分
- 【算法一】
- 有10%的数据,所有数字都在 \(10^9\) 以内,直接做就行了。
- 时间复杂度 \(O(nl)\),期望得分 \(10\) 分。
- 【算法二】
- 由于答案是模 \(10^m\) 的,所以把所有数都模 \(10^m\) 答案不变。于是现在所有数字都在 \(10^{18}\) 以内,直接做就行了。不过可能会遇到两个\(10^{18}\) 以内的数相乘,如果不想写高精度就用快速乘算法。
- 时间复杂度 \(O(nl \log_2(10^{18}))\),期望得分 \(30\) 分。
- 【算法三】
- 写高精度,并压位。
- 时间复杂度 \(O(nl({m \over w})^2)\),其中 \(w\) 为压的位数。期望得分 \(60\) 分。
- 【算法四】
- 把算法三中的高精度乘法用FFT等算法实现。
- 时间复杂度 \(O(nl{m \over w} \log_2m)\),常数超大,期望得分 \(60 \sim 80\) 分。
- 【算法五】(标准算法)
- 本题的关键是通过差分把乘法转化成加减法。
- 把 \(f(x)\) 差分,即令多项式 \(g(x) = f(x + 1) - f(x)\),得到的 \(g(x)\) 是一个 \(n - 1\) 次多项式,不妨定义其为 \(f^{(n-1)}(x)\) 。
- 同理,差分两次后得到一个 \(n-2\) 次多项式,设其为 \(f^{(n-2)}(x)\)
- ……
- 这样下去,差分 \(n\)次后就能得到一些常数。
- 令\(a[i][j] = f(i)(