少项式技术

其实就是一些平方暴力的多项式运算，以防某些人在数据范围允许平方时拍 NTT 上去。刚好出题用到了少项式技术就象征地总结一下。

普通幂少项式

单点求值

struct poly : vector<mint> {
  using vector::vector;
  mint operator()(const mint& x) const {
    auto&& f = *this;
    mint res = 0, now = 1;
    for (int i = 0; i < (int)f.size(); i++) res += now * f[i], now *= x - i;
    return res;
  }
};

整除与取模

将被除式的每一个高位，尝试用除式的某一倍数去减，使其消失。

poly operator/(poly lhs, const poly& rhs) {
  if (lhs.size() < rhs.size()) return {};
  mint iz = 1 / rhs.back();
  vector<mint> ret(lhs.size() - rhs.size() + 1);
  for (int i = (int)lhs.size() - 1; i >= (int)rhs.size() - 1; i--) {
    auto k = ret[i - rhs.size() + 1] = lhs[i] * iz;
    for (int j = 0; j < (int)rhs.size(); j++) lhs[i - j] -= rhs[rhs.size() - j - 1] * k;
  }
  return ret;
}

拉格朗日插值

根据不知道哪里来的实践经验，拉插特有的除二项式部分需要特别优化。

poly divide2(poly lhs, mint b) {
  vector<mint> ret(lhs.size() - 1);
  for (int i = (int)lhs.size() - 1; i >= 1; i--) {
    auto k = ret[i - 1] = lhs[i];
    lhs[i - 1] -= b * k;
  }
  return ret;
}
poly lagrange(const vector<pair<mint, mint>>& vec) {
  poly ans(vec.size()), prod{1};
  for (int i = 0; i < (int)vec.size(); i++) prod = prod * poly{0 - vec[i].first, 1};
  for (int i = 0; i < (int)vec.size(); i++) {
    mint den = 1;
    for (int j = 0; j < (int)vec.size(); j++) {
      if (i != j) den *= vec[i].first - vec[j].first;
    }
    auto num = divide2(prod, 0 - vec[i].first);
    auto k = vec[i].second / den;
    for (int j = 0; j < (int)vec.size(); j++) ans[j] += num[j] * k;
  }
  return ans;
}

对数与指数

【模板】子集卷积 - caijianhong - 博客园

根据求导公式比较两边系数。

下降幂少项式

单点求值

struct poly : vector<mint> {
  using vector::vector;
  mint operator()(const mint& x) const {
    auto&& f = *this;
    mint res = 0, now = 1;
    for (int i = 0; i < (int)f.size(); i++) res += now * f[i], now *= x - i;
    return res;
  }
};

普通幂转下降幂

使用第二类斯特林数。

从阶乘幂到斯特林数 - caijianhong - 博客园

poly nor2under(const poly& f) {
  poly g(f.size());
  for (int i = 0; i < (int)f.size(); i++) {
    for (int j = 0; j <= i; j++) g[j] += S[i][j] * f[i];
  }
  return g;
}
S[0][0] = 1;
for (int i = 1; i <= 2000; i++) {
  for (int j = 1; j <= i; j++) S[i][j] = S[i - 1][j] * j + S[i - 1][j - 1];
}

下降幂转普通幂

使用第一类斯特林数并携带某个系数。

poly under2nor(const poly& f) {
  poly g(f.size());
  for (int i = 0; i < (int)f.size(); i++) {
    for (int j = 0; j <= i; j++) g[j] += S1[i][j] * ((i - j) & 1 ? -1 : +1) * f[i];
  }
  return g;
}
S1[0][0] = 1;
for (int i = 1; i <= 2000; i++) {
  for (int j = 1; j <= i; j++) S1[i][j] = S1[i - 1][j] * (i - 1) + S1[i - 1][j - 1];
}

点值平移

\(f(x)\to f(x-b)\)。观察到下降幂也有二项式定理。

poly translate(const poly& f, int b) {
  poly g(f.size());
  for (int i = 0; i < (int)f.size(); i++) {
    mint now = 1;
    for (int j = 0; j <= i; j++) {
      g[i - j] += f[i] * binom(i, j) * now;
      now *= -b - j;
    }
  }
  return g;
}

有限微积分相关

有限微积分与数列求和 - 洛谷专栏