药烷

sol

  • f_n 表示n个点的答案.

这里不妨另f_0 = 1.

因为这样我们就可以强制所有的树上节点都存在3个儿子.

如果没写n\leq 500的请出门左转.

不难考虑出答案的生成函数:

A(x)=1+x\cdot {A(x)^3+3A(x^2)A(x)+2A(x^3)\over 6}

  • 注意补上常数项
  1. 分治fft这是肯定可以的 O(n\log^2 n)
  2. 牛顿迭代O(n\log n)

这里介绍第二种.

所谓的多项式牛顿迭代, 个人理解为在\bmod x^{2n}意义下

将求解前已知的多项式视为常数.

如此题求出了B_0(x) \bmod x ^ n那么B_0(x^2), B_0(x^3) \bmod x^{2n}都是已知多项式.

那么F'(A(x)) 就会求了.

Code

#include 
using namespace std;
typedef long long LL;
typedef vector poly;

const int N = 1 << 18 | 10;
const int mod = 998244353;

namespace {
  inline int mul(int a, int b) { return (LL) a * b % mod; }
  inline int add(int a, int b) { return (a += b) < mod ? a : a - mod; }
  inline int sub(int a, int b) { return (a -= b) < 0 ? a + mod : a; }
  inline int Pow(int a, int b) {
    int r = 1;
    for(; b; b >>= 1, a = mul(a, a))
      if(b & 1) r = mul(r, a);
    return r;
  }
  inline void read(int &x) {
    x = 0; char c = getchar();
    for(;!isdigit(c); c = getchar());
    for(; isdigit(c); c = getchar())
      x = add(mul(x, 10), c - '0');
  }
}

inline void print(poly &a) {
  for(int i = 0; i < (int) a.size(); ++i)
    printf("%d ", a[i]);
  puts("");
}

int n;
namespace PO {
  int lim, rev[N], o[N >> 1];
  inline void init(int n) {
    for(lim = 1; lim < n; lim <<= 1);
    for(int i = 0, s = lim >> 1; i < lim; ++i)
      rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? s : 0);
    o[0] = 1;
    int c = :: Pow(3, (mod - 1) / lim);
    for(int i = 1; i < lim >> 1; ++i)
      o[i] = mul(o[i - 1], c);
  }
  void Dft(poly &a, int n = lim) {
    static int t;
    for(int i = 0; i < n; ++i)
      if(i < rev[i]) swap(a[i], a[rev[i]]);
    for(int m = 1, tmp = n >> 1; m < n; m <<= 1, tmp >>= 1)
      for(int i = 0; i < n; i += m << 1) {
        int *l = &a[0] + i, *r = l + m;
        for(int k = 0; k < m; ++k, ++l, ++r) {
            t = mul(*r, o[tmp * k]);
            *r = sub(*l, t);
            *l = add(*l, t);
        }
      }
  }
  void Idft(poly &a, int n = lim) {
    reverse(a.begin() + 1, a.end());
    Dft(a);
    int Iv = :: Pow(n, mod - 2);
    for(int i = 0; i < (int) a.size(); ++i)
      a[i] = mul(a[i], Iv);
  }
  poly Mul(poly a, poly b) {
    int n = a.size(), m = b.size();
    init(n + m - 1);
    a.resize(lim), Dft(a);
    b.resize(lim), Dft(b);
    for(int i = 0; i < lim; ++i)
      a[i] = mul(a[i], b[i]);
    Idft(a);
    a.resize(n + m - 1);
    return a;
  }
  poly Inv(poly a, int O) {
    if(!a[0]) { cerr << "no Inv!\n"; }
    poly b(1, :: Pow(a[0], mod - 2)), c;
    for(int i = 2; (i >> 1) < O; i <<= 1) {
      init(i << 1);
      c = a, c.resize(i);
      b.resize(i << 1), Dft(b);
      c.resize(i << 1), Dft(c);
      for(int j = 0; j < (i << 1); ++j)
                b[j] = mul(b[j], sub(2, mul(b[j], c[j])));
      Idft(b);
      b.resize(i);
    }
    b.resize(O);
    return b;
  }
    inline poly Add(poly a, poly b) {
        int n = (int) max(a.size(), b.size());
        a.resize(n);
        b.resize(n);
        for(int i = 0; i < n; ++i)
            a[i] = add(a[i], b[i]);
        return a;
    }
    inline poly Sub(poly a, poly b) {
        int n = (int) max(a.size(), b.size());
        a.resize(n);
        b.resize(n);
        for(int i = 0; i < n; ++i)
            a[i] = sub(a[i], b[i]);
        return a;
    }

    poly solve(int n) {
        if(n == 1) return poly(2, 1);
        poly a = solve(n + 1 >> 1);
        poly b(n + 1, 0), c(n + 1, 0);
        for(int i = 0; i * 2 <= n; ++i)
            b[i << 1] = mul(3, a[i]);
        for(int i = 0; i * 3 <= n; ++i)
            c[i + (i << 1)] = mul(2, a[i]);

        poly d;
        d = Mul(a, Mul(a, a)); d.resize(n + 1);
        d = Add(d, Mul(a, b)); d.resize(n + 1);
        d = Add(d, c); d.resize(n + 1);
        static int iv6 = :: Pow(6, mod - 2);
        d.resize(d.size() + 1);
        for(int i = (int) d.size() - 1; ~i; --i)
            d[i + 1] = mul(d[i], iv6);
        d[0] = 1;
        d = Sub(d, a);

        poly e;
        e = Mul(a, a);
        for(int i = 0; i < (int) e.size(); ++i)
            e[i] = mul(e[i], 3);
        e = Add(e, b);
        e.resize(e.size() + 1);
        for(int i = (int) e.size() - 1; ~i; --i)
            e[i + 1] = mul(e[i], iv6);
        e[0] = sub(0, 1);
        e.resize(n + 1);

        d = Mul(d, Inv(e, n + 1));
        a = Sub(a, d);
        a.resize(n + 1);
        return a;
    }

  void main() {
    read(n);
    poly a = solve(n);
    printf("%d\n", a[n]);
  }
}

int main() {
  PO :: main();
  return 0;
}