けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ ???? Many Parentheses (KUPC 2020 M)

形式的冪級数の pow で通せた!

問題概要

 N 個の箱それぞれに正しい括弧列を入れる。ただし、次の2つの条件をともに満たすように入れる必要がある。

  •  N 個の箱に含まれる '(' の個数の合計が  M
  • 長さが  2K である括弧列はどの箱にも入れてはならない

条件を満たす入れ方の総数を 998244353 で割ったあまりを求めよ。

制約

  •  1 \le N \le 10^{6}
  •  1 \le K \le M \le 10^{6}

考えたこと

長さが  2k となる「正しいカッコ列」の個数はカタラン数と呼ばれるもの ( c(k) と書くことにする)。

 c(k) = \frac{{}_{2n}{\rm C}_{n}}{n+1}

が成り立つ。

mathtrain.jp

そして、今回の問題は形式的冪級数の知見を活用すると、

  •  f(x) = c(0) + c(1)x^{1} + c(2)x^{2} + \dots + c(M)x^{M} (ただし  c(K)x^{K} の項のみ除く)

として、 \lbrack x^{M} \rbrack f(x)^{N} を求めれば OK だとわかる。そしてこれは  O(M \log M) で求められる。yosupo juege から速い FPS のコードを借用することで通った!!

しかし実際には、 O(N + M) で求められる解法があったらしくて、すごい!!!

http://www.kupc.jp/static/media/M.0bed529c.pdf