結果

問題 No.1193 Penguin Sequence
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2020-08-22 16:44:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,119 ms / 2,000 ms
コード長 3,149 bytes
コンパイル時間 370 ms
コンパイル使用メモリ 81,964 KB
実行使用メモリ 164,500 KB
最終ジャッジ日時 2024-10-15 10:47:02
合計ジャッジ時間 32,187 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,000 ms
162,268 KB
testcase_01 AC 1,108 ms
164,500 KB
testcase_02 AC 1,092 ms
163,680 KB
testcase_03 AC 1,101 ms
163,796 KB
testcase_04 AC 1,108 ms
163,936 KB
testcase_05 AC 1,098 ms
164,056 KB
testcase_06 AC 1,096 ms
164,156 KB
testcase_07 AC 1,096 ms
164,316 KB
testcase_08 AC 1,106 ms
164,428 KB
testcase_09 AC 1,119 ms
164,104 KB
testcase_10 AC 1,105 ms
164,168 KB
testcase_11 AC 656 ms
116,864 KB
testcase_12 AC 675 ms
117,248 KB
testcase_13 AC 952 ms
132,824 KB
testcase_14 AC 882 ms
126,760 KB
testcase_15 AC 1,032 ms
140,032 KB
testcase_16 AC 916 ms
114,876 KB
testcase_17 AC 37 ms
51,968 KB
testcase_18 AC 171 ms
80,640 KB
testcase_19 AC 1,102 ms
164,004 KB
testcase_20 AC 861 ms
126,284 KB
testcase_21 AC 744 ms
121,380 KB
testcase_22 AC 198 ms
83,840 KB
testcase_23 AC 623 ms
116,736 KB
testcase_24 AC 553 ms
108,288 KB
testcase_25 AC 300 ms
91,904 KB
testcase_26 AC 144 ms
78,592 KB
testcase_27 AC 931 ms
131,556 KB
testcase_28 AC 692 ms
121,472 KB
testcase_29 AC 950 ms
132,684 KB
testcase_30 AC 394 ms
102,196 KB
testcase_31 AC 339 ms
95,664 KB
testcase_32 AC 780 ms
126,976 KB
testcase_33 AC 568 ms
112,128 KB
testcase_34 AC 476 ms
109,056 KB
testcase_35 AC 585 ms
112,768 KB
testcase_36 AC 480 ms
108,800 KB
testcase_37 AC 912 ms
127,016 KB
testcase_38 AC 39 ms
52,224 KB
testcase_39 AC 38 ms
51,968 KB
testcase_40 AC 39 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

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 * inverse(modnCr(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 * inverse(modnCr(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 * inverse(modnCr(N,i)) * modnCr(N-2,i-2) * rev
    nex %= mod

print ((ans + nex) % mod)
0