競技プログラミング用 知識集積所
ABC411E - E［max］
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
期待値（未作成）を求めるには、全ての出目について「その目の値*その目が最大値になる確率」を求め、合計すればよい。
ただし、同じ大きさの目については、適当に大小関係を設けることにする。
今回は確率の分母が6^nであることから、「その目の値*その目が最大値になる目の出方」を合計して6^nで割ればよい。
ただし、同じ大きさの目については、適当に大小関係を設けることにする。
今回は確率の分母が6^nであることから、「その目の値*その目が最大値になる目の出方」を合計して6^nで割ればよい。
目の出方は、全ての目について「他の各サイコロで、その目より小さいものがいくつあるかを数えて、その全ての積」を考えればよい。
（もちろん、同じ大きさの目には、先ほど設定した大小関係でもって「小さい」かどうか判定する）
これは逐一計算しなくても、目の大きさが大きい順に処理することにすれば、「他の各サイコロの未処理の目の個数の積」でよい。
そしてそれは、「全サイコロの未処理の目の個数の積」を「自身の未処理の目の個数の積」で割ればよい。
（もちろん、同じ大きさの目には、先ほど設定した大小関係でもって「小さい」かどうか判定する）
これは逐一計算しなくても、目の大きさが大きい順に処理することにすれば、「他の各サイコロの未処理の目の個数の積」でよい。
そしてそれは、「全サイコロの未処理の目の個数の積」を「自身の未処理の目の個数の積」で割ればよい。
したがって、priority_queueで6*n個の目を大きい順に取り出しながら、「全サイコロの未処理の目の個数の積」を更新しながら、「その目の値*その目が最大値になる目の出方」を計算していけばよい。
最後に6^nで割り算すれば答えとなる。
最後に6^nで割り算すれば答えとなる。
答えは998244353で割った余りを要求されているので、剰余類換（未作成）の考えに従って処理する。
何か足し算や掛け算をするたびに結果を%998244353し、割り算は代わりに998244353-2乗したものを掛ける。
累乗計算を何度も行うため、高速累乗（未作成）のアルゴリズムも用意しておくこと。
何か足し算や掛け算をするたびに結果を%998244353し、割り算は代わりに998244353-2乗したものを掛ける。
累乗計算を何度も行うため、高速累乗（未作成）のアルゴリズムも用意しておくこと。
