ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ARC106 D - Powers (畳み込み解)

問題
提出コード

解法

まずは式を分解していきます。ループの中、つまり(A_{L} + A_{R})^{X}に注目すると、これは二項定理そのもので
\displaystyle (A_{L} + A_{R})^{X} =  \sum_{i = 0}^{X} \,_{X}C_{i}A_{L}^{i}A_{R}^{X-i}
となり、さらにコンビネーションを分解すると、
\displaystyle \sum_{i = 0}^{X} \left( X! \times \frac{A_{L}^{i}}{i!} \times \frac{A_{R}^{X-i}}{(X-i)!}\right)
となります。X!は最後にかければよいので、\frac{A_{L}^{i}}{i!} \times \frac{A_{R}^{X-i}}{(X-i)!}の部分が高速に計算できればよいです。
ここから、答えを計算しやすくするため、ループの部分のインデックスをいじることについて考えます。

  • \displaystyle \sum_{L=1}^{N-1}\sum_{R=L+1}^{N}(A_{L} + A_{R})^{X}

  • \displaystyle \sum_{L=1}^{N}\sum_{R=1}^{N}(A_{L} + A_{R})^{X}

上記の2つの式を比較すると、上の式を2倍した後、\sum_{i=1}^{N}(A_{i} + A_{i})^{X}を足したものが下の式になっています。
なので、下の式が求められれば、上の式の値もなんとか求められそうだ、となります。この後は下の式を計算することについて考えていきましょう。
ループの中の式について、分解した後のものを当てはめてみます。
\displaystyle X! \times \sum_{L=1}^{N}\sum_{R=1}^{N}\sum_{i = 0}^{X} \left(  \frac{A_{L}^{i}}{i!} \times \frac{A_{R}^{X-i}}{(X-i)!}\right)
結局、以下の値を求められれば良いことになります。
\displaystyle X! \times \sum_{i = 0}^{X} \left(  \sum_{L=1}^{N}\frac{A_{L}^{i}}{i!} \times \sum_{R=1}^{N}\frac{A_{R}^{X-i}}{(X-i)!}\right)
よって、\displaystyle B_{i} = \sum_{p=1}^{N}\frac{A_{p}^{i}}{i!}とすることで、
\displaystyle X! \times \sum_{i = 0}^{X} \left(  B_{i} \times B_{X-i}\right)
となり、シグマの部分が畳み込みの式そのものになっています。
よって、NTTを用いてこれを計算すれば、\sum_{L=1}^{N}\sum_{R=1}^{N}(A_{L} + A_{R})^{X}が求まることがわかりました。
さて、この値を2で割った後、最後に\sum_{i=1}^{N}(A_{i} + A_{i})^{X}を引かなければなりません。ですが、こちらは以下のように式変形します。
\displaystyle \sum_{i=1}^{N}(A_{i} + A_{i})^{X} = \sum_{i=1}^{N}\left(A_{i}^{X} \times \sum_{p=0}^{X}\,_{X}C_{p}\right)
最初と同様、コンビネーションを分解し、
\displaystyle \sum_{i=1}^{N}\left(A_{i}^{X}X! \times \sum_{p=0}^{X}\left(\frac{1}{p!} \times \frac{1}{(X-p)!}\right)\right)
とすると、同様に畳み込みの式が出てくるので、NTTを用いて計算できます。
まぁ、2A_{i}X乗すれば良いですが…
ということで、これで全ての欲しい式がそろったので、あとは計算するだけです。

感想

NTT、FFTは最近始めたばかりなので、今回の問題を自力でコンテスト中に通せたのは嬉しいです。
コンビネーションがNTTに落とし込めるのを既に学習していたのが大きいかもしれません。
逆に、想定解の方法が全然思い浮かびませんでした…