给你一个大小为\(n\)的集合\({c_1, c_2,\ldots ,c_n}\)，规定合法的二叉树为带点权且点权都属于给定集合中的点的数。对于任意整数$i\in [1, m]$，求出有多少不同的点权和为\(i\)的二叉树并输出之。

\(1\leq n, m, c_i\leq 10^5\)。

第一次搞出来多项式求逆以外的多项式牛顿迭代了……

先构造那个集合的生成函数：

\[C(x) = \sum_{i = 1}^{+\infty} [i\in S]x^i\]

那么考虑构造各种点权和的生成函数。首先我们需要放进去空二叉树的方案，其他情况下一定是一个根下面接上两个二叉树，所以生成函数\(F(x)\)满足：

\[F(x) = F^2(x)C(x) + 1\]

用初中数学背的公式可以得到：

\[F(x) = \frac{1\pm\sqrt{1 - 4C(x)}}{2C(x)}\]

那么那个正负号到底是啥呢？我们注意到如果取加号的话，那么有\(\lim_{x\rightarrow 0} F(x) = +\infty\)，这显然与\(F(x)\)的常数项为\(1\)的事实不符；而取减号时有\(\lim_{x\rightarrow 0}F(x) = 1\)，这样才是对的。

那么多项式求逆已经是传统艺能了，那么就讨论一下多项式开根怎么搞吧！

注意到我们这些题往往是知道了一个多项式\(P(x)\)，要求你求出满足\(G(F(x))\equiv 0\pmod{x^p}\)（\(G(x)\)为一个和\(P(x)\)有关的限制的函数）的多项式\(F(x)\)。我们对于这类东西往往使用倍增的手段，首先对于膜\(x\)的情况往往是很好处理的。我们接下来就要从膜\(x^{t}\)的多项式推到膜\(x^{2t}\)的多项式，我们假设这两个多项式分别为\(F_0(x)\)和\(F(x)\)，那么我们将\(G(x)\)在\(F_0(x)\)处做泰勒展开，得到：

\[
\begin{aligned}
G(F(x))&\equiv G(F_0(x)) + \frac{G'(F_0(x))}{1!}(F(x) - F_0(x))^1 +\ldots\pmod{x^{2t}}\\
G(F(x))&\equiv G(F_0(x)) + G'(F_0(x))(F(x) - F_0(x))\pmod{x^{2t}}\\
G'(F_0(x))F(x)&\equiv G'(F_0(x))F_0(x) - G(F_0(x))\pmod{x^{2t}}\\
F(x)&\equiv F_0(x) - \frac{G(F_0(x))}{G'(F_0(x))}\pmod{x^{2t}}
\end{aligned}
\]

（注意一下……上面的导数是将多项式当做数意义下的导数，所以出现在\(G(x)\)中的常多项式在求导之后会被消掉）

如此一来，我们就得到了倍增的手段，对于这个题有\(G(t) = t^2 - C\)，那么带进去得到：

\[F(x) = F_0(x) - \frac{F_0^2(x) - C(x)}{2F_0(x)} = \frac{F_0^2(x) + C(x)}{2F_0(x)}\]

还有一个问题就是这个东西要求膜\(x\)的情况下的多项式很容易套出来……但是答案生成函数需要求\(2C(x)\)的逆元，这玩意常数项为\(0\)没法正常求逆……所以我们变一下，分式上下都乘上\(1 + \sqrt{1 - 4C(x)}\)，就得到了\(\frac{2}{1 + \sqrt{1 - 4C(x)}}\)，这个式子就没那么多麻烦事了……

多项式开根本来就有很多细节问题需要注意……具体参考代码吧……

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
using ll = long long;
const ll ha = 998244353LL;
ll pow_mod(ll a, ll b) {
  ll ans = 1, res = a;
  while(b) {
    if(1LL & b) ans = ans * res % ha;
    res = res * res % ha; b >>= 1;
  }
  return ans;
}
ll inv(ll x) {
  return pow_mod(x, ha - 2LL);
}

int flip(int bi, int x) {
  int ans = 0;
  for(int j = 0; j < bi; j ++) {
    if((1 << j) & x) {
      ans |= (1 << (bi - j - 1));
    }
  }
  return ans;
}
void NTT(ll *A, int bi, bool flag = false) {
  int n = 1 << bi;
  for(int i = 0; i < n; i ++) {
    int v = flip(bi, i);
    if(v < i) std::swap(A[v], A[i]);
  }
  for(int L = 1; L < n; L <<= 1) {
    ll xi_n = pow_mod(3LL, (ha - 1LL) / (ll(L << 1)));
    if(flag) xi_n = inv(xi_n);
    for(int i = 0; i < n; i += (L << 1)) {
      ll xi = 1LL;
      for(int j = i; j < i + L; j ++) {
        ll x = A[j], y = A[j + L];
        ll tmp = y * xi % ha;
        A[j] = (x + tmp) % ha;
        A[j + L] = (x - tmp + ha) % ha;
        xi = xi * xi_n % ha;
      }
    }
  }
  if(flag) {
    ll inv_n = inv(n);
    for(int i = 0; i < n; i ++) {
      A[i] = A[i] * inv_n % ha;
    }
  }
}

const int maxn = 400050;
void poly_inv(int mod, ll *B, ll *BB) {
  if(mod == 1) {
    BB[0] = inv(B[0]);
  } else {
    poly_inv((mod + 1) >> 1, B, BB);
    int bi = 0, sz = 1;
    while(sz <= ((mod * 2) + 1)) {
      bi ++; sz <<= 1;
    }
    static ll tmp[maxn];
    std::copy(B, B + mod, tmp);
    std::fill(tmp + mod, tmp + sz, 0LL);
    NTT(tmp, bi); NTT(BB, bi);
    for(int i = 0; i < sz; i ++) {
      tmp[i] = (tmp[i] * BB[i]) % ha;
      tmp[i] = (tmp[i] * (ha - 1LL)) % ha;
      tmp[i] = (tmp[i] + 2LL) % ha;
      tmp[i] = (tmp[i] * BB[i]) % ha;
    }
    NTT(tmp, bi, true);
    std::copy(tmp, tmp + mod, BB);
    std::fill(BB + mod, BB + sz, 0LL);
  }
}
void poly_sqrt(int mod, ll *B, ll *BB) {
  if(mod == 1) {
    BB[0] = 1LL;
  } else {
    poly_sqrt((mod + 1) >> 1, B, BB);
    int bi = 0, sz = 1;
    while(sz <= (mod * 2 + 1)) {
      bi ++; sz <<= 1;
    }
    std::fill(BB + (mod + 1) / 2, BB + sz, 0LL);
    
    ll *up = (ll*)calloc(maxn, sizeof(ll));
    std::copy(BB, BB + sz, up);
    NTT(up, bi);
    for(int i = 0; i < sz; i ++) up[i] = up[i] * up[i] % ha;
    NTT(up, bi, true);
    // std::fill(up + mod, up + sz, 0LL);
    static const ll inv_2 = inv(2);
    for(int i = 0; i < mod; i ++) up[i] = ((up[i] + B[i]) % ha) * inv_2 % ha;
    
    ll *tmp = (ll*)calloc(maxn, sizeof(ll));
    ll *down = (ll*)calloc(maxn, sizeof(ll));
    std::copy(BB, BB + sz, tmp);
    poly_inv(mod, tmp, down);
    
    NTT(up, bi); NTT(down, bi);
    for(int i = 0; i < sz; i ++) up[i] = up[i] * down[i] % ha;
    NTT(up, bi, true);
    std::copy(up, up + mod, BB);
    std::fill(up + mod, up + sz, 0LL);
    free(up); free(tmp); free(down);
  }
}

ll A[maxn], B[maxn], C[maxn];
int main() {
  int n, m; scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; i ++) {
    int x; scanf("%d", &x);
    C[x] = (C[x] - 4LL + ha) % ha;
  }
  C[0] = 1LL;
  poly_sqrt(m + 1, C, B);
  B[0] = (B[0] + 1LL) % ha;
  poly_inv(m + 1, B, A);
  for(int i = 1; i <= m; i ++) {
    printf("%I64d\n", (2LL * A[i]) % ha);
  }
  return 0;
}

• 相关文章
• 全局相关文章