yukicoder No.940 ワープ ε=ε=ε=ε=ε=│;p>д＜│

予約投稿なので初投稿です

リンク

yukicoder.me

TL;DR;

指数型母関数と形式的べき級数を知っていますか？僕は知っています。

前提

以下では 0<X+Y+Z=N$0<X+Y+Z=N$ を仮定します（なんでこの制約ないねん）

ちょうど n$n$ 回の移動でたどり着く通り数を an$a_n$ と置きます。

まず、ちょうど n$n$ 回という条件が面倒なので、 n$n$ 回以下の移動でたどり着く通り数 bn$b_n$ を考えます。
重複組み合わせの公式から、bn=(X+n−1n−1)(Y+n−1n−1)(Z+n−1n−1)$b_n=(\genfrac{}{}{0ex}{}{X+n-1}{n-1})(\genfrac{}{}{0ex}{}{Y+n-1}{n-1})(\genfrac{}{}{0ex}{}{Z+n-1}{n-1})$ であることがわかります。
ある n$n$ に対し、 ak(k<n)$a_k(k<n)$ が全て分かっているなら、 an=bn−∑k=1n−1(nk)ak$a_n=b_n-{\displaystyle \sum _{k=1}^{n-1}(\genfrac{}{}{0ex}{}{n}{k})a_k}$ を用いて an$a_n$ を求めることができます。計算量は O(N2)$O(N^2)$ です。

指数型母関数サイコー！一番好きな母関数です。

以下、 f(x)=∑n=0∞anxnn!,g(x)=∑n=0∞bnxnn!$f(x)={\displaystyle \sum _{n=0}^{\mathrm{\infty }}{a}_n\frac{x^n}{n!},g(x)={\displaystyle \sum _{n=0}^{\mathrm{\infty }}{b}_n\frac{x^n}{n!}}}$ とおきます。
（これは係数にbinomがあることから指数型母関数を知っていればある程度自然な発想だと思います）

すると、形式的べき級数として考えた時に、以下の等式が成り立ちます

f(x)(1+x+x2/2+x3/6...)=f(x)exp(x)=g(x)$f(x)(1+x+x^2/2+x^3/\mathrm{6...})=f(x)\exp (x)=g(x)$

したがって、 形式的べき級数として exp(x)exp(−x)=1$\exp (x)\exp (-x)=1$ であることを用いて

f(x)=g(x)exp(−x)$f(x)=g(x)\exp (-x)$

です。今回は先頭のたかだか N$N$ 項を求めれば十分なので、 g(x)=∑n=0∞(X+n−1n−1)(Y+n−1n−1)(Z+n−1n−1)xnn!$g(x)={\displaystyle \sum _{n=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{X+n-1}{n-1})(\genfrac{}{}{0ex}{}{Y+n-1}{n-1})(\genfrac{}{}{0ex}{}{Z+n-1}{n-1})\frac{x^n}{n!}}$ と exp(−x)=∑n=0∞(−x)nn!=∑n=0∞(−1)nxnn!$\exp (-x)={\displaystyle \sum _{n=0}^{\mathrm{\infty }}\frac{(-x{)}^n}{n!}={\displaystyle \sum _{n=0}^{\mathrm{\infty }}(-1{)}^n\frac{x^n}{n!}}}$ の先頭 N$N$ 項を陽に計算し、その積を求めればいいです。

計算量はFFTなどを用いることで O(NlogN)$O(NlogN)$ になります。

おまけ

exp(x)$\exp (x)$ の逆数を求めるのにFPSライブラリを貼るとTLEする（一敗）
FFTの精度がdoubleだと足りない（一敗）

提出URL

yukicoder.me