Simple C++(17) implementation for univariate formal power series computation in competitive programming.↵
↵
[a.hpp](https://wandbox.org/permlink/WAah8SMFjYEqovQT) with `main` function.↵
↵
Idea from fjzzq2002's [blog](https://fjzzq2002.blog.uoj.ac/blog/7281) (in Chinese). My code is about 2 times slower than fjzzq2002's, but mine is shorter and simpler.↵
↵
I am glad if you would toldell me about bugs or optimizations.↵
↵
## Usage↵
↵
GF for Catalan numbers [A000108](https://oeis.org/A000108).↵
↵
```cpp↵
#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](https://oeis.org/A000598).↵
↵
```cpp↵
#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](https://oeis.org/A000081).↵
↵
```cpp↵
#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](https://oeis.org/A144036).↵
↵
```cpp↵
#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](https://creativecommons.org/publicdomain/zero/1.0/).↵
↵
## Reference↵
↵
- Daniel J. Bernstein. [The tangent FFT](https://cr.yp.to/arith/tangentfft-20070919.pdf).↵
- J. van der Hoeven. [Relax, but don’t be too lazy](https://www.sciencedirect.com/science/article/pii/S0747717102905626). JSC, 34:479–542, 2002.↵
- van der Hoeven, J., 2003a. [New algorithms for relaxed multiplication](http://www.texmacs.org/joris/newrelax/newrelax.html). Tech. Rep. 2003–44, Universit´e Paris-Sud, Orsay, France.↵
- Philippe Flajolet and Robert Sedgewick. [Analytic Combinatorics](http://algo.inria.fr/flajolet/).
↵
[a.hpp](https://wandbox.org/permlink/WAah8SMFjYEqovQT) with `main` function.↵
↵
Idea from fjzzq2002's [blog](https://fjzzq2002.blog.uoj.ac/blog/7281) (in Chinese). My code is about 2 times slower than fjzzq2002's, but mine is shorter and simpler.↵
↵
I am glad if you would t
↵
## Usage↵
↵
GF for Catalan numbers [A000108](https://oeis.org/A000108).↵
↵
```cpp↵
#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](https://oeis.org/A000598).↵
↵
```cpp↵
#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](https://oeis.org/A000081).↵
↵
```cpp↵
#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](https://oeis.org/A144036).↵
↵
```cpp↵
#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](https://creativecommons.org/publicdomain/zero/1.0/).↵
↵
## Reference↵
↵
- Daniel J. Bernstein. [The tangent FFT](https://cr.yp.to/arith/tangentfft-20070919.pdf).↵
- J. van der Hoeven. [Relax, but don’t be too lazy](https://www.sciencedirect.com/science/article/pii/S0747717102905626). JSC, 34:479–542, 2002.↵
- van der Hoeven, J., 2003a. [New algorithms for relaxed multiplication](http://www.texmacs.org/joris/newrelax/newrelax.html). Tech. Rep. 2003–44, Universit´e Paris-Sud, Orsay, France.↵
- Philippe Flajolet and Robert Sedgewick. [Analytic Combinatorics](http://algo.inria.fr/flajolet/).
