Simple C++(17) implementation for univariate formal power series computation in competitive programming.

a.hpp with main function.

Idea from fjzzq2002's blog (in Chinese). My code is about 2 times slower than fjzzq2002's, but mine is shorter and simpler.

I am glad if you would tell me about bugs or optimizations.

There are several mistakes in the comments of the code ... sorry.

Usage

GF for Catalan numbers A000108.

#include <iostream>
#include "a.hpp"
int main() {
  using lib::Mint;
  using lib::FPS;
  FPS<Mint<998244353>> A;
  auto X = FPS<Mint<998244353>>::idm();
  A.reset().set(X / (1 - A));
  for (int i = 0; i <= 10; ++i) std::cout << A[i] << ' ';
}

GF for alkyl A000598.

#include <iostream>
#include "a.hpp"
int main() {
  using lib::Mint;
  using lib::FPS;
  FPS<Mint<998244353>> A;
  auto X = FPS<Mint<998244353>>::idm();
  A.reset().set((A.pow(3) / 6 + A * A(X ^ 2) / 2 + A(X ^ 3) / 3) * X + 1);
  for (int i = 0; i <= 10; ++i) std::cout << A[i] << ' ';
}

GF for unlabeled trees A000081.

#include <iostream>
#include "a.hpp"
int main() {
  using lib::Mint;
  using lib::FPS;
  FPS<Mint<998244353>> A;
  auto X = FPS<Mint<998244353>>::idm();
  A.reset().set(A.Exp() * X);
  auto B = A - (A * A - A(X ^ 2)) / 2;
  for (int i = 0; i <= 10; ++i) std::cout << B[i] << ' ';
}

Apply Euler transform several times A144036.

#include <iostream>
#include "a.hpp"
int main() {
  using lib::Mint;
  using lib::FPS;
  FPS<Mint<998244353>> A;
  auto X = FPS<Mint<998244353>>::idm();
  A.reset().set((((A.Exp() - 1).Exp() - 1).Exp() - 1).Exp() * X);
  for (int i = 0; i <= 10; ++i) std::cout << A[i] << ' ';
}

License

CC0 1.0.

Reference

• Daniel J. Bernstein. The tangent FFT.
• J. van der Hoeven. Relax, but don’t be too lazy. JSC, 34:479–542, 2002.
• van der Hoeven, J., 2003a. New algorithms for relaxed multiplication. Tech. Rep. 2003–44, Universit´e Paris-Sud, Orsay, France.
• Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics.