ABC240 G - Teleporting Takahashi (600)
コンテスト中の考察
$ X,Y,Z方向の移動を$ i回選んだ場合をそれぞれ$ x_i,y_i,z_iとする
求める値は$ N! \sum_i^n x_i^{-1} \sum_j^{n-i} y_j^{-1} z_{n-i-j}^{-1}
$ \sum_j^{n-i} y_j^{-1} z_{n-i-j}^{-1}の部分はFFTで高速に求められるので、各$ x_iについてFFTで値を求めれば解ける
3つWAが出て駄目
解説の解法
低い次元から考える
一次元の場合、$ N \ge XでN,Xの偶奇が合っていれば$ {}_nC_{\frac{n-x}{2}}
二次元の場合、$ U = \frac{X+Y}{2}, V = \frac{X-Y}{2}とすると、U,Vが独立に考えられるので一次元の場合と同様に考えられる
三次元の場合、各$ Xの移動回数について考えると残りのY,Zは二次元の場合と同様に考えられる
二次元以下の場合は階乗とその逆元を事前に求めておくと$ \mathcal{O}(1)で求まるので、三次元の場合は$ \mathcal{O}(N)で求まる