コンテンツにスキップ

DOJ Starter Contest 1 H - 수열 안 정렬하기 2

サイト
DOJ
コンテスト
DOJ Starter Contest 1
問題
H - 수열 안 정렬하기 2

長さ NN の整数列 AA を並べ替えて作れる異なる数列のうち、広義単調増加ではないものの個数を求める問題です。同じ値の要素は区別しません(N≤105N\le10^5)。答えは 101210^{12} 以下であることが保証されています。

値 vv の出現回数を cvc_v とすると、異なる並べ方の総数は

P=N!∏vcv!P=\frac{N!}{\prod_v c_v!}

です。要素を区別した並べ方 N!N! から、同じ値同士の入れ替えによる重複を除いています。

このうち広義単調増加な並べ方は、昇順にソートした 11 通りだけです。よって、答えは P−1P-1 です。

コードでは、大きな階乗をそのまま計算する代わりに、p=109+7p=10^9+7 と q=109+9q=10^9+9 のそれぞれを法として PP の余りを求めています。

どちらの素数も NN より大きいため、cv!c_v! は法の倍数になりません。したがって逆元が存在し、分母の逆元を掛けることで割り算できます。pow(t, -1, m) が、法 mm での tt の逆元を求めています。

関数 q(m) では階乗を法 mm で前計算し、P mod mP\bmod m を返します。

小さい答えの保証を使って復元する

Section titled “小さい答えの保証を使って復元する”

P mod p=xP\bmod p=x、P mod q=yP\bmod q=y とすると、PP はある非負整数 ii を使って

P=pi+xP=pi+x

と書けます。そこで ii を順に試し、(pi+x) mod q=y(pi+x)\bmod q=y になるものを探します。

答えが 101210^{12} 以下なので、P≤1012+1P\le10^{12}+1 です。よって i=⌊P/p⌋<1000i=\lfloor P/p\rfloor<1000 であり、コードの range(10**4) で必ず見つかります。また、この探索範囲の候補はすべて pqpq 未満です。異なる2つの素数を法とする余りが両方一致する数は pqpq 未満の範囲で一意なので、見つかった候補が PP そのものです。

最後に 11 を引いて答えを出力します。計算量は、ハッシュ表の平均的な操作時間を仮定すると、階乗と出現回数の計算が O(N)O(N)、逆元計算が各法について O(log⁡m)O(\log m)、復元の探索が高々 10410^4 回です。

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