### hly1204's blog

By hly1204, history, 13 months ago,

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] << ' ';
}