結果

問題 No.1193 Penguin Sequence
コンテスト
ユーザー 👑 SPD_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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

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