Simple C++ implementation for univariate formal power series in cp

Revision en3, by hly1204, 2022-02-20 18:44:29

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

Tags power series

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English hly1204 2022-02-20 18:44:29 69
en2 English hly1204 2022-02-20 18:39:59 4 fix typo
en1 English hly1204 2022-02-20 18:31:40 2565 Initial revision (published)