betrue12 https://blog.hatena.ne.jp/betrue12/ ARMERIA https://betrue12.hateblo.jp/ AtCoder プログラミング 競技プログラミング お題箱より。 F - Count Permutations Many Times 難しめの（とはいえ上級者には比較的知名度が高い）テクニックを複数使いこなす必要がある問題です。公式解説では多項式の係数に対応させて解いていますが、そうではない方法で説明しようと思います。 解法 まずは1つのクエリだけを考える まずはこの問題を、あるクエリ（区間） 1つだけについて解くことを考えましょう。 「 である」よりも「 である（違反状態である）」のほうが数えやすいので、包除原理を適用します。 個の整数の集合を として、その部分集合 を考えます。 に含まれる整数が全て違反状態である（含まれない整数はどちらでも… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbetrue12.hateblo.jp%2Fentry%2F2019%2F12%2F24%2F010258" title="第一回日本最強プログラマー学生選手権決勝 F - Count Permutations Many Times - 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=%20%28L%2C%20R%29 Hatena Blog https://hatena.blog 2019-12-24 01:02:58 rich https://betrue12.hateblo.jp/entry/2019/12/24/010258 1.0 100%