結果

問題 No.1193 Penguin Sequence
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2020-08-22 16:47:26
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 523 ms / 2,000 ms
コード長 3,184 bytes
コンパイル時間 246 ms
コンパイル使用メモリ 82,156 KB
実行使用メモリ 164,300 KB
最終ジャッジ日時 2024-10-15 10:50:18
合計ジャッジ時間 16,182 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 415 ms
162,540 KB
testcase_01 AC 517 ms
164,172 KB
testcase_02 AC 506 ms
163,668 KB
testcase_03 AC 520 ms
164,036 KB
testcase_04 AC 515 ms
164,060 KB
testcase_05 AC 519 ms
163,796 KB
testcase_06 AC 523 ms
164,052 KB
testcase_07 AC 502 ms
164,048 KB
testcase_08 AC 512 ms
164,300 KB
testcase_09 AC 497 ms
163,912 KB
testcase_10 AC 505 ms
164,052 KB
testcase_11 AC 334 ms
116,992 KB
testcase_12 AC 339 ms
117,244 KB
testcase_13 AC 437 ms
132,448 KB
testcase_14 AC 410 ms
126,912 KB
testcase_15 AC 473 ms
140,320 KB
testcase_16 AC 337 ms
114,676 KB
testcase_17 AC 39 ms
52,736 KB
testcase_18 AC 119 ms
80,640 KB
testcase_19 AC 510 ms
163,544 KB
testcase_20 AC 401 ms
126,108 KB
testcase_21 AC 357 ms
121,216 KB
testcase_22 AC 122 ms
83,584 KB
testcase_23 AC 312 ms
116,736 KB
testcase_24 AC 273 ms
108,288 KB
testcase_25 AC 170 ms
92,160 KB
testcase_26 AC 105 ms
77,696 KB
testcase_27 AC 432 ms
131,568 KB
testcase_28 AC 344 ms
121,984 KB
testcase_29 AC 439 ms
132,452 KB
testcase_30 AC 211 ms
101,888 KB
testcase_31 AC 191 ms
95,616 KB
testcase_32 AC 376 ms
126,952 KB
testcase_33 AC 281 ms
112,128 KB
testcase_34 AC 250 ms
109,568 KB
testcase_35 AC 287 ms
112,488 KB
testcase_36 AC 243 ms
109,148 KB
testcase_37 AC 415 ms
127,040 KB
testcase_38 AC 38 ms
52,352 KB
testcase_39 AC 38 ms
52,608 KB
testcase_40 AC 36 ms
52,352 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

"""

それぞれの数字を右端として、どれだけ転倒数に寄与するか調べたい
i回目の操作で選ばれた時、元々自分より左の数に関しては

まず、自分の組に入っていないのを計算する
残りは全体を計算しておいて逆算する

NCi-1 * (NC1 * 残り + NC2 * 残り + … + i-1Ci-2 * 残り)
→右は大体同じなのでO(N)でいける

全てのiについて計算したら、組の数と掛け合わせて終わり


自分の組に入っているのは
i番目の組で成立するのは
NC2 * 残り

"""

from sys import stdin
import sys

mod = 998244353

def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 1～aまでの和を求める
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret

def inverse(a): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる)

    return fac[n] * inv[n-r] * inv[r] % mod

def invnCr(n,r):
    return inv[n] * fac[n-r] * fac[r] % mod

N = int(stdin.readline())
A = list(map(int,stdin.readline().split()))
#Aを座圧する
tmpdic = {}
tmpnum = []
for i in A:
    if i not in tmpdic:
        tmpdic[i] = 1
        tmpnum.append(i)
tmpnum.sort()
for i in range(len(tmpnum)):
    tmpdic[tmpnum[i]] = i
for i in range(N):
    A[i] = tmpdic[A[i]]
#print (A , file = sys.stderr)

fac,inv = modfac(N+10,mod)

ALM = 1 #全ての選び方
for i in range(1,N+1):
    ALM *= modnCr(N,i)
    ALM %= mod

ans = 0

#自分の組でないのを数える
pair = N*(N-1)//2 #数字が異なるペアの数
tmpdic = {}
for i in A:
    if i not in tmpdic:
        tmpdic[i] = 1
    else:
        tmpdic[i] += 1
for i in tmpdic:
    pair -= tmpdic[i] * (tmpdic[i]-1) // 2

#i番目であるペアがペアになりうる通り数を数える
#j番目だけNC(j-1)が掛かってる選び方→j番目にある数がある数え方をリストに
pickone = []

for i in range(1,N+1):
    pickone.append( ALM * invnCr(N,i) * modnCr(N-1,i-1) % mod )

#pickoneのj番目 < iまでの和を変形してj,iでペアになる通り数を計算する
onepairs = 0
tmpsum = 0
for i in range(1,N+1):
    onepairs += tmpsum * invnCr(N,i) * modnCr(N-1,i-1) % mod
    #print (onepairs)
    onepairs %= mod
    tmpsum += pickone[i-1]

ans = onepairs * pair % mod
#print (pickone , onepairs , pair)


#自分の組を数える
rev = 0
BIT = [0] * (N+10)
for i in range(N):
    rev += i - bitsum(A[i]+2,BIT)
    bitadd(A[i]+2,1,BIT)

nex = 0
for i in range(2,N+1):
    nex += ALM * invnCr(N,i) * modnCr(N-2,i-2) * rev
    nex %= mod

print ((ans + nex) % mod)
0