コンテスト中の考察 $ 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で値を求めれば解ける