結果
問題 | No.1311 Reverse Permutation Index |
ユーザー |
![]() |
提出日時 | 2020-12-08 20:34:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 43 ms / 1,500 ms |
コード長 | 1,571 bytes |
コンパイル時間 | 180 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 52,992 KB |
最終ジャッジ日時 | 2024-09-18 18:14:47 |
合計ジャッジ時間 | 1,060 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 6 |
ソースコード
import sysinput = sys.stdin.readlineN, S = map(int, input().split())class BIT:def __init__(self, n):self.n = nself.data = [0] * (n + 1)self.el = [0] * (n + 1)def sum(self, i):s = 0while i > 0:s += self.data[i]i -= i & -ireturn sdef add(self, i, x):self.el[i] += xwhile i <= self.n:self.data[i] += xi += i & -idef get(self, i, j = None):if j is None:return self.el[i]return self.sum(j) - self.sum(i)def lowerbound(self, s):x = 0y = 0for i in range(self.n.bit_length(), -1, -1):k = x + (1 << i)if k <= self.n and (y + self.data[k] < s):y += self.data[k]x += 1 << ireturn x + 1class numeroBIT:def __init__(self, mx):self.mx = mxself.fwk = BIT(mx)def add(self, x): self.fwk.add(x, 1)def discard(self, x):if self.fwk.get(x): self.fwk.add(x, -1)def kthmax(self, k):n = self.fwk.sum(self.mx)return self.fwk.lowerbound(n - k + 1)nfwk = numeroBIT(S)for x in range(1, S + 1): nfwk.add(x)f = 1for i in range(1, S): f *= ia = []for i in range(S - 1, -1, -1):x = nfwk.kthmax(i + 1 - N // f)nfwk.discard(x)a.append(x)N %= fif i: f //= i#print(a)b = []for i in range(S):for j in range(S):if i + 1 == a[j]:b.append(j + 1)break#print(b)for x in range(1, S + 1): nfwk.add(x)for i in range(1, S): f *= ires = 0for i in range(S):x = b[i]y = nfwk.fwk.sum(x) - 1res += y * fnfwk.discard(x)if S - i - 1: f //= (S - i - 1)print(res)