P4893 Derivatives Solution

· · 题解

来水一波 Python 题解（自带高精度的功能好爽，而且本题不用 FFT）

这题读入很毒瘤，不是直接读入系数，而是读入整个函数！更令人意想不到的是函数还有同类项！！！（我当时就是因为这个 WA 的）我在我的代码中还加入了负系数，以及一次项与常数项指数的省略。虽然本题不需要，但是这份代码可以供我后续做数学题所需。

不过读入后面的事情就小菜一碟了。求导可以用：

f(x)&=a_nx^n+a_{n-1}x^{n-1}+a_{n-2}x^{n-2}\dots+a_1x+a_0 \\f^{(k)}(x)&=a_nn^{\underline{k}}x^{n-k}+a_{n-1}(n-1)^{\underline{k}}x^{n-k-1}+a_{n-2}(n-2)^{\underline{k}}x^{n-k-2}+\dots+a_{k+1}(k+1)^{\underline{k}}x+a_kk! \end{aligned}

暴力求解即可。时间复杂度 O(n^2)。

带入计算时，为尽可能运用分配律，我们可以选择 秦九韶算法，也就是：

f(x)&=a_nx^n+a_{n-1}x^{n-1}+a_{n-2}x^{n-2}\dots+a_1x+a_0 \\&=x(x(\dots (x(x\times a_n+a_{n-1})+a_{n-2})\dots)+ a_1)+a_0 \end{aligned}

所有询问时间复杂度总和 O(nm)。

所以总时间复杂度 O(n^2+nm)。真实时间复杂度要更高，因为有高精（尽管 Python 自带），然而 Python 能过。

代码如下：

n,k=input().split(' ')
n,k=int(n),int(k)
f=input()
g=[0 for i in range(n+1)]
i=5
while i<len(f):
  d=1
  sign=1
  while i<len(f) and (ord(f[i])<48 or ord(f[i])>=58) and f[i]!='-' and f[i]!='x':
    i+=1
  if f[i]=='-':
    sign=-1
    i+=1
  x=i
  while i<len(f):
    try:
      d=int(f[x:i+1])
    except:
      break
    i+=1
  if d==0:
    d=1
  d*=sign
  e=0
  if i<len(f) and f[i]=='x':
    e=1
  while i<len(f) and (ord(f[i])<48 or ord(f[i])>=58) and f[i]!='+' and f[i]!='-':
    i+=1
  x=i
  while i<len(f):
    try:
      e=int(f[x:i+1])
    except:
      break
    i+=1
  g[e]+=d #I wrote g[e]=d and got a WA!
# print(g)
for i in range(k,n+1):
  for j in range(i,i-k,-1):
    g[i]*=j
del g[0:k]
# print(g)
m=int(input())
for i in range(m):
  x=int(input())
  s=0
  for j in g[::-1]:
    s=s*x+j
  print(s)