betrue12 https://blog.hatena.ne.jp/betrue12/ ARMERIA https://betrue12.hateblo.jp/ Codeforces プログラミング 競技プログラミング Problem - F - Codeforces 問題概要 問の問題からなるコンテストがある。 番目の問題の正解者数は、区間 に含まれる整数の中から等確率で決まる。 問題 の正解者数が広義単調減少になる確率を求めよ。これは有理数になるため、 で出力せよ。 制約 解法 問題 の正解者数を と書くことにします。確率よりも場合の数のほうが計算しやすいので、条件を満たすような数列 の総数（場合の数）を計算して全事象数で割ることにします。 DPができそうですが、 が非常に大きいのが厄介です。座標圧縮ができないか考えましょう。 座標圧縮後に扱いやすくするため、入力の に 加算して半開区間 として考えます。… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbetrue12.hateblo.jp%2Fentry%2F2020%2F02%2F01%2F023051" title="Educational Codeforces Round 81 F. Good Contest - ARMERIA" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%20n Hatena Blog https://hatena.blog 2020-02-01 02:30:51 rich https://betrue12.hateblo.jp/entry/2020/02/01/023051 1.0 100%