DOJ Starter Contest 1 H - 수열 안 정렬하기 2
- サイト
- DOJ
- コンテスト
- DOJ Starter Contest 1
- 問題
- H - 수열 안 정렬하기 2
長さ の整数列 を並べ替えて作れる異なる数列のうち、広義単調増加ではないものの個数を求める問題です。同じ値の要素は区別しません()。答えは 以下であることが保証されています。
重複を除いた順列の個数
Section titled “重複を除いた順列の個数”値 の出現回数を とすると、異なる並べ方の総数は
です。要素を区別した並べ方 から、同じ値同士の入れ替えによる重複を除いています。
このうち広義単調増加な並べ方は、昇順にソートした 通りだけです。よって、答えは です。
2つの素数で余りを求める
Section titled “2つの素数で余りを求める”コードでは、大きな階乗をそのまま計算する代わりに、 と のそれぞれを法として の余りを求めています。
どちらの素数も より大きいため、 は法の倍数になりません。したがって逆元が存在し、分母の逆元を掛けることで割り算できます。pow(t, -1, m) が、法 での の逆元を求めています。
関数 q(m) では階乗を法 で前計算し、 を返します。
小さい答えの保証を使って復元する
Section titled “小さい答えの保証を使って復元する”、 とすると、 はある非負整数 を使って
と書けます。そこで を順に試し、 になるものを探します。
答えが 以下なので、 です。よって であり、コードの range(10**4) で必ず見つかります。また、この探索範囲の候補はすべて 未満です。異なる2つの素数を法とする余りが両方一致する数は 未満の範囲で一意なので、見つかった候補が そのものです。
最後に を引いて答えを出力します。計算量は、ハッシュ表の平均的な操作時間を仮定すると、階乗と出現回数の計算が 、逆元計算が各法について 、復元の探索が高々 回です。
Python
from collections import Counter
N = int(input())A = list(map(int, input().split()))C = Counter(A)
def q(m): l = [1] for i in range(N): l.append(l[-1] * (i + 1) % m) res = l[N] t = 1 for i in C.values(): t = t * l[i] % m res = res * pow(t, -1, m) % m return res
x = q(10**9 + 7)y = q(10**9 + 9)for i in range(10**4): if ((10**9 + 7) * i + x) % (10**9 + 9) == y: print((10**9 + 7) * i + x - 1) break