多项式(polynomial)

多项式(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)(
上一篇:一天一个 Linux 命令(20):sed 命令


下一篇:nl