結果

問題 No.1193 Penguin Sequence
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2020-08-22 16:47:26
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 548 ms / 2,000 ms
コード長 3,184 bytes
コンパイル時間 365 ms
コンパイル使用メモリ 82,308 KB
実行使用メモリ 164,572 KB
最終ジャッジ日時 2024-04-23 10:54:35
合計ジャッジ時間 17,008 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 438 ms
162,652 KB
testcase_01 AC 540 ms
164,440 KB
testcase_02 AC 532 ms
163,916 KB
testcase_03 AC 537 ms
164,044 KB
testcase_04 AC 535 ms
164,048 KB
testcase_05 AC 534 ms
164,048 KB
testcase_06 AC 535 ms
163,668 KB
testcase_07 AC 537 ms
163,920 KB
testcase_08 AC 537 ms
164,572 KB
testcase_09 AC 539 ms
164,168 KB
testcase_10 AC 548 ms
164,300 KB
testcase_11 AC 336 ms
116,992 KB
testcase_12 AC 352 ms
117,120 KB
testcase_13 AC 457 ms
132,968 KB
testcase_14 AC 429 ms
126,776 KB
testcase_15 AC 521 ms
149,312 KB
testcase_16 AC 345 ms
115,008 KB
testcase_17 AC 39 ms
52,480 KB
testcase_18 AC 115 ms
80,800 KB
testcase_19 AC 532 ms
163,804 KB
testcase_20 AC 423 ms
126,108 KB
testcase_21 AC 379 ms
121,344 KB
testcase_22 AC 126 ms
83,712 KB
testcase_23 AC 322 ms
116,864 KB
testcase_24 AC 287 ms
108,160 KB
testcase_25 AC 171 ms
92,032 KB
testcase_26 AC 102 ms
78,088 KB
testcase_27 AC 452 ms
131,444 KB
testcase_28 AC 356 ms
121,728 KB
testcase_29 AC 457 ms
132,836 KB
testcase_30 AC 213 ms
102,240 KB
testcase_31 AC 198 ms
95,776 KB
testcase_32 AC 400 ms
127,156 KB
testcase_33 AC 301 ms
112,384 KB
testcase_34 AC 255 ms
109,440 KB
testcase_35 AC 297 ms
112,512 KB
testcase_36 AC 248 ms
109,184 KB
testcase_37 AC 438 ms
126,932 KB
testcase_38 AC 38 ms
52,352 KB
testcase_39 AC 38 ms
52,736 KB
testcase_40 AC 38 ms
52,608 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