結果
問題 | No.2068 Restricted Permutation |
ユーザー |
👑 |
提出日時 | 2022-09-02 22:02:18 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 148 ms / 2,000 ms |
コード長 | 2,381 bytes |
コンパイル時間 | 314 ms |
コンパイル使用メモリ | 82,396 KB |
実行使用メモリ | 126,848 KB |
最終ジャッジ日時 | 2024-11-16 03:29:56 |
合計ジャッジ時間 | 4,390 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
# https://atcoder.jp/contests/code-festival-2016-qualc/submissions/33924036from bisect import bisectclass Bit:def __init__(self, n):self.size = nself.n0 = 1 << (n.bit_length() - 1)self.tree = [0] * (n + 1)def range_sum(self, l, r):return self.sum(r - 1) - self.sum(l - 1)def sum(self, i):i += 1s = 0while i > 0:s += self.tree[i]i -= i & -ireturn sdef get(self, i):return self.sum(i) - self.sum(i - 1)def add(self, i, x):i += 1while i <= self.size:self.tree[i] += xi += i & -idef lower_bound(self, x):pos = 0plus = self.n0while plus > 0:if pos + plus <= self.size and self.tree[pos + plus] < x:x -= self.tree[pos + plus]pos += plusplus //= 2return posMOD = 998244353N = 2000000fact = [0 for _ in range(N)]invfact = [0 for _ in range(N)]fact[0] = 1for i in range(1, N):fact[i] = fact[i - 1] * i % MODinvfact[N - 1] = pow(fact[N - 1], MOD - 2, MOD)for i in range(N - 2, -1, -1):invfact[i] = invfact[i + 1] * (i + 1) % MODdef nCk(n, k):if k < 0 or n < k:return 0else:return (fact[n] * invfact[k] % MOD) * invfact[n - k] % MODdef nPk(n, k):if k < 0 or n < k:return 0else:return fact[n] * invfact[n - k] % MODdef nHk(n, k):if n == k == 0:return 1return nCk(n + k - 1, k)n, k, x = map(int, input().split())P = [0] * nP[k - 1] = xP = P[::-1]tf = [False] * (n + 1)ind = []for i, p in enumerate(P):tf[p] = Truelst = []for i in range(1, n + 1):if not tf[i]:lst.append(i)inv2 = pow(2, MOD - 2, MOD)ans = 0l = len(lst)invl = pow(l, MOD - 2, MOD)bit = Bit(n + 1)x = 0t = 0for i, p in enumerate(P):if p == 0:ans += (x * fact[i]) * inv2 % MODans %= MODx += 1ans += (t * fact[i] % MOD) * invl % MODans %= MODelse:c = bit.sum(p)ans += fact[i] * c % MODans %= MODbit.add(p, 1)c = bisect(lst, p)ans += (c * invl % MOD) * (fact[i] * x % MOD) % MODans %= MODt += l - cans *= fact[l]ans %= MODprint(ans)