进度可见 pastebin

分治卷积

考虑分治

$$ f_i=\sum_{mid}\sum_{j=l}^{mid}f_j\times g_{i-j} $$

防止 $l$ 前的元素的干扰,截取有效部分做卷积。

时间复杂度 $\mathcal O(nlog^2n)$

void solve(int l, int r) {
  if (l == r) 
    return;
  int mid = (l + r) >> 1;
  solve(l, mid);
  for (int i = 0; i <= r - l; i++)
    A[i] = B[i] = 0; 
  for (int i = 0; i <= mid - l; ++i)
    A[i] = f[i + l];
  for (int i = 0; i <= r - l; ++i)
    B[i] = g[i];
  DFT(A, r - l + 1), DFT(B, r - l + 1);
  for (int i = 0; i <= r - l; ++i)
    A[i] = (ll)A[i] * B[i] % mod;
  IDFT(A, r - l + 1);
  for (int i = mid + 1; i <= r; ++i)
    f[i] = (f[i] + A[i - l]) % mod; 
  solve(mid + 1, r);
}

多项式乘法逆

$$ A\times B\equiv 1 (\mathrm{mod}\; x^n) $$

考虑分治,已知 $B'$

$$ A\times B'\equiv 1(\mathrm {mod} \;x^\frac n2) $$

$$ A\times (B-B')\equiv 0(\mathrm{mod} \; x^\frac n2) $$

$$ B-B'\equiv 0(\mathrm {mod}\; x^\frac n2) $$

$$ B^2-2B\times B'+B'^2\equiv 0(\mathrm {mod} \; x^n) $$

$$ B-2B'+AB'^2\equiv 0(\mathrm {mod} \; x^n) $$

$$ B\equiv2B'-AB'^2 $$

时间复杂度 $\mathcal O(\mathrm {nlogn})$

poly inv(poly a, int n) {
  a.resize(n); 
  if (n == 1) 
    return poly(1, Inv(a[0], p));
  else {
    poly b = inv(a, n + 1 >> 1);
    b = b * (2 - a * b); 
    b.resize(n); 
    return b; 
  }
}

多项式对数函数

$$ B(x)\equiv \ln(A(x)) (\mathrm {mod} \; x^n) $$

考虑对等式两遍进行求导,右边链式法则求导

$$ B'(x)\equiv \frac {A'(x)}{A(x)} $$

然后两边分别积分即可

时间复杂度为 $\mathcal O(\mathrm {nlogn})$

poly derivative(poly a) {
  poly res(a.size() - 1); 
  for (unsigned i = 0; i < res.size(); ++i) res[i] = (long long)a[i + 1] * (i + 1) % p;
  return res; 
}

poly integral(poly a) {
  poly res(a.size() + 1, 0);
  for (unsigned i = 1; i < res.size(); ++i) res[i] = (long long)a[i - 1] * Inv(i) % p; 
  return res; 
}

poly ln(poly a) {
  poly res = integral(~a * derivative(a)); 
  res.resize(a.size()); 
  return res; 
}
最后修改:2020 年 08 月 22 日 11 : 31 PM
如果觉得我的文章对你有用,请随意赞赏