結果
問題 | No.1193 Penguin Sequence |
ユーザー | qumazaki |
提出日時 | 2020-09-16 03:07:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 785 ms / 2,000 ms |
コード長 | 2,835 bytes |
コンパイル時間 | 792 ms |
コンパイル使用メモリ | 86,980 KB |
実行使用メモリ | 154,616 KB |
最終ジャッジ日時 | 2023-09-04 03:15:49 |
合計ジャッジ時間 | 25,835 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 381 ms
150,872 KB |
testcase_01 | AC | 773 ms
153,324 KB |
testcase_02 | AC | 768 ms
154,496 KB |
testcase_03 | AC | 785 ms
153,016 KB |
testcase_04 | AC | 769 ms
154,616 KB |
testcase_05 | AC | 767 ms
153,012 KB |
testcase_06 | AC | 778 ms
154,496 KB |
testcase_07 | AC | 771 ms
153,092 KB |
testcase_08 | AC | 781 ms
153,088 KB |
testcase_09 | AC | 772 ms
153,156 KB |
testcase_10 | AC | 778 ms
154,508 KB |
testcase_11 | AC | 447 ms
110,896 KB |
testcase_12 | AC | 431 ms
111,144 KB |
testcase_13 | AC | 661 ms
146,616 KB |
testcase_14 | AC | 570 ms
122,296 KB |
testcase_15 | AC | 727 ms
153,208 KB |
testcase_16 | AC | 301 ms
140,356 KB |
testcase_17 | AC | 95 ms
80,468 KB |
testcase_18 | AC | 160 ms
86,400 KB |
testcase_19 | AC | 751 ms
152,088 KB |
testcase_20 | AC | 567 ms
121,116 KB |
testcase_21 | AC | 485 ms
115,312 KB |
testcase_22 | AC | 169 ms
87,128 KB |
testcase_23 | AC | 411 ms
109,588 KB |
testcase_24 | AC | 368 ms
104,064 KB |
testcase_25 | AC | 233 ms
94,036 KB |
testcase_26 | AC | 150 ms
84,508 KB |
testcase_27 | AC | 653 ms
144,320 KB |
testcase_28 | AC | 454 ms
114,132 KB |
testcase_29 | AC | 657 ms
144,288 KB |
testcase_30 | AC | 282 ms
98,924 KB |
testcase_31 | AC | 263 ms
94,980 KB |
testcase_32 | AC | 523 ms
117,848 KB |
testcase_33 | AC | 375 ms
107,412 KB |
testcase_34 | AC | 322 ms
100,928 KB |
testcase_35 | AC | 380 ms
105,884 KB |
testcase_36 | AC | 317 ms
100,140 KB |
testcase_37 | AC | 623 ms
139,404 KB |
testcase_38 | AC | 97 ms
80,364 KB |
testcase_39 | AC | 95 ms
80,360 KB |
testcase_40 | AC | 98 ms
80,364 KB |
ソースコード
class fenwick_tree(): def __init__(self, n:int, mod:int = 0): self.__mod = mod self.__n = n self.__data = [0] * self.__n def add(self, p:int, x:int): assert (0 <= p) & (p < self.__n) if(self.__mod == 0): self.__add_mod0(p,x) else: self.__add_mod(p,x) def __add_mod0(self, p:int, x:int): p+=1 while( p<= self.__n): self.__data[p-1] += x p += p & -p def __add_mod(self, p:int, x:int): p+=1 while( p<= self.__n): self.__data[p-1] += x self.__data[p-1] %= self.__mod p += p & -p def sum(self, l:int, r:int): assert (0 <= l) & (l <= r) & (r <= self.__n) if(self.__mod == 0): return self.__sum_mod0(r) - self.__sum_mod0(l) else: return self.__sum_mod(r) - self.__sum_mod(l) def __sum_mod0(self, r:int): s = 0 while(r > 0): s += self.__data[r-1] r -= r & -r return s def __sum_mod(self, r:int): s = 0 while(r > 0): s += self.__data[r-1] s %= self.__mod r -= r & -r return s n = int(input()) a = list(map(int,input().split())) mod = 998244353 ## nCkのmodを求める関数 # テーブルを作る(前処理) max_n = 2 * 10**5 + 100 fac, finv, inv = [0]*max_n, [0]*max_n, [0]*max_n def comInit(max_n): fac[0] = fac[1] = 1 finv[0] = finv[1] = 1 inv[1] = 1 for i in range(2,max_n): fac[i] = fac[i-1]* i% mod inv[i] = mod - inv[mod%i] * (mod // i) % mod finv[i] = finv[i-1] * inv[i] % mod comInit(max_n) # 二項係数の計算 def com(n,k): if(n < k): return 0 if( (n<0) | (k < 0)): return 0 return fac[n] * (finv[k] * finv[n-k] % mod) % mod inverse = 0 a_ind = [[ai,i] for i,ai in enumerate(a)] a_ind.sort(key= lambda x: -1*x[0]*10**6 - x[1]) d = {} bit = fenwick_tree(n) for ai,i in a_ind: inverse += bit.sum(0,i+1) bit.add(i,1) if(not ai in d): d[ai] = 1 else: d[ai] += 1 inverse %= mod inverse_all = n*(n-1)//2 for i in d.values(): inverse_all -= i*(i-1)//2 inverse_all %= mod combs = [1] * (n+1) comb_l = [1] * (n+1) comb_r = [1] * (n+2) one = [0] * (n+1) pair = [0] * (n+1) for i in range(1,n+1): combs[i] = com(n,i) comb_l[i] = (comb_l[i-1] * combs[i])%mod one[i] = com(n-1,i-1) pair[i] = com(n-2,i-2) for i in range(n,0,-1): comb_r[i] = (comb_r[i+1]*combs[i])%mod ans = 0 ones = 0 for i in range(1,n+1): ans += ones * inverse_all * comb_r[i+1] * one[i] ans %= mod ones = (ones * combs[i] + comb_l[i-1] * one[i])%mod # print(i,ans) ans += pair[i] * inverse * comb_l[i-1] * comb_r[i+1] ans %= mod # print(i,ans) print(ans)