yukicoder contest 218 F - 増える演算 - 情報妖精の競プロ日記

F問題の解説です。

問題

問題文(要約)

問題文

$\frac{\prod_{i=1}^{N} \prod_{j=i+1}^{N} (A_i + A_j) \cdot A_i^{A_j}}{\underset{i < j}{\min}((A_i + A_j) \cdot A_i^{A_j})} \mod 1000000007$$ を求めよ。

制約

$2 \leq N \leq 10^5$
$1 \leq A_i \leq 10^5$

全部が掛け算の形になるように解いていくことを考えます。
まず、指数の部分です。
これは $i$ を決め打つと $A_i^{\sum_{j=i+1}^{N} A_j}$ となり、累積和があると ${\rm O}(N \log A_i)$ で構築できます。
これにより、まずは指数部について解が求まりました。
次に、和の部分です。
これは個数に関しては畳み込み演算が可能なので、FFTを用いると高速に個数が分かります。
最後に、minの部分です。
これは必ず $A_i$ を決め打った時 $A_j$ は最小を選んでることを利用すると、適当な比較関数を用いて求めることができます。
よって、全部が積の形になったので後は掛ければ答えが求まります。

感想

テストケースの
3
1 5 3
が可能なんじゃないかという話から、30分で作った問題でした。
サンプル3、入力が3153で出力が6000なの凄いと思いません？
個人的には色々と詰め込んでいる上にFFTとかも出てくるので難しいかなと思いましたが、上位勢にとってはやっぱり簡単なようですね。
まぁ私からは難しかった、ということで……。
実際、tester提示の★3からは上がり、★4.5に届いたようですし。