hly1204's blog

By hly1204, history, 2 years ago, In English

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

  • Vote: I like it
  • +40
  • Vote: I do not like it

| Write comment?
»
14 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Recently I also tried to implement fjzzq's idea, the end product is here.

It presents a somehow more verbose interface, but it's conceptually (and actually) faster than fjzzq's original implementation since it does not use shared_ptr(s).

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Maybe I'm missing something, but I couldn't find what the exact idea proposed by fjzzq is (I don't understand Chinese so perhaps something was lost in translation?).

    Is it similar to this blog and its comments? If not, is there an English reference for the idea? Thanks!

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It should be, though in literature it's known as "fully-online convolution", not attributed to Danqi CHEN.

      I think fjzzq's proposal is mostly about the implementation, not the algorithmic idea itself, since it's widely recognized that online convolution can be useful in modern competitive programming. In particular, it emphasized that with enough engineering effort, we can solve most generating function evaluation task with ease.

      To summarize, hly and I are talking about how to implement online convolution to provide a clean API to use, not what to implement.