ARC106 D - Powers (畳み込み解)
解法
まずは式を分解していきます。ループの中、つまりに注目すると、これは二項定理そのもので
となり、さらにコンビネーションを分解すると、
となります。は最後にかければよいので、の部分が高速に計算できればよいです。
ここから、答えを計算しやすくするため、ループの部分のインデックスをいじることについて考えます。
上記の2つの式を比較すると、上の式を2倍した後、を足したものが下の式になっています。
なので、下の式が求められれば、上の式の値もなんとか求められそうだ、となります。この後は下の式を計算することについて考えていきましょう。
ループの中の式について、分解した後のものを当てはめてみます。
結局、以下の値を求められれば良いことになります。
よって、とすることで、
となり、シグマの部分が畳み込みの式そのものになっています。
よって、NTTを用いてこれを計算すれば、が求まることがわかりました。
さて、この値を2で割った後、最後にを引かなければなりません。ですが、こちらは以下のように式変形します。
最初と同様、コンビネーションを分解し、
とすると、同様に畳み込みの式が出てくるので、NTTを用いて計算できます。
まぁ、を乗すれば良いですが…
ということで、これで全ての欲しい式がそろったので、あとは計算するだけです。
感想
NTT、FFTは最近始めたばかりなので、今回の問題を自力でコンテスト中に通せたのは嬉しいです。
コンビネーションがNTTに落とし込めるのを既に学習していたのが大きいかもしれません。
逆に、想定解の方法が全然思い浮かびませんでした…
D、最近でぐわーさんのPDFでAGCのコンビネーションを分解してNTTに投げる問題やったおかげで解けた
— ツバサ (@emtsu_ba) 2020年10月24日