結果

問題 No.1193 Penguin Sequence
ユーザー 👑 SPD_9X2SPD_9X2
提出日時 2020-08-22 16:44:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,139 ms / 2,000 ms
コード長 3,149 bytes
コンパイル時間 287 ms
コンパイル使用メモリ 82,572 KB
実行使用メモリ 164,780 KB
最終ジャッジ日時 2024-04-23 10:51:37
合計ジャッジ時間 33,150 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,021 ms
162,712 KB
testcase_01 AC 1,134 ms
164,780 KB
testcase_02 AC 1,139 ms
163,784 KB
testcase_03 AC 1,138 ms
164,464 KB
testcase_04 AC 1,134 ms
164,112 KB
testcase_05 AC 1,126 ms
164,060 KB
testcase_06 AC 1,125 ms
163,972 KB
testcase_07 AC 1,125 ms
164,116 KB
testcase_08 AC 1,128 ms
164,432 KB
testcase_09 AC 1,128 ms
163,964 KB
testcase_10 AC 1,136 ms
164,392 KB
testcase_11 AC 672 ms
117,328 KB
testcase_12 AC 684 ms
117,116 KB
testcase_13 AC 998 ms
133,104 KB
testcase_14 AC 906 ms
126,956 KB
testcase_15 AC 1,059 ms
140,128 KB
testcase_16 AC 927 ms
115,208 KB
testcase_17 AC 40 ms
53,172 KB
testcase_18 AC 173 ms
80,888 KB
testcase_19 AC 1,121 ms
163,876 KB
testcase_20 AC 878 ms
126,468 KB
testcase_21 AC 750 ms
121,828 KB
testcase_22 AC 199 ms
84,132 KB
testcase_23 AC 633 ms
117,040 KB
testcase_24 AC 561 ms
108,628 KB
testcase_25 AC 304 ms
92,064 KB
testcase_26 AC 144 ms
79,132 KB
testcase_27 AC 937 ms
131,472 KB
testcase_28 AC 700 ms
121,964 KB
testcase_29 AC 962 ms
132,936 KB
testcase_30 AC 399 ms
102,152 KB
testcase_31 AC 342 ms
96,040 KB
testcase_32 AC 788 ms
127,176 KB
testcase_33 AC 575 ms
112,360 KB
testcase_34 AC 483 ms
109,512 KB
testcase_35 AC 594 ms
112,756 KB
testcase_36 AC 471 ms
109,240 KB
testcase_37 AC 923 ms
127,340 KB
testcase_38 AC 39 ms
52,800 KB
testcase_39 AC 42 ms
53,440 KB
testcase_40 AC 39 ms
53,220 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