結果

問題 No.2250 Split Permutation
ユーザー lam6er
提出日時 2025-03-26 16:00:03
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,384 bytes
コンパイル時間 445 ms
コンパイル使用メモリ 82,388 KB
実行使用メモリ 126,768 KB
最終ジャッジ日時 2025-03-26 16:01:08
合計ジャッジ時間 6,282 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 15 TLE * 1 -- * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD = 998244353

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    P = list(map(int, input[1:N+1]))
    
    # Precompute pow2
    max_pow = N
    pow2 = [1] * (max_pow + 1)
    for i in range(1, max_pow + 1):
        pow2[i] = (pow2[i-1] * 2) % MOD
    
    # Compute K (number of inversion pairs in original permutation)
    class FenwickTree:
        def __init__(self, size):
            self.size = size
            self.tree = [0] * (self.size + 2)
        
        def update(self, idx, val=1):
            while idx <= self.size:
                self.tree[idx] += val
                idx += idx & -idx
        
        def query(self, idx):
            res = 0
            while idx > 0:
                res += self.tree[idx]
                idx -= idx & -idx
            return res
    
    ft = FenwickTree(N)
    K = 0
    for i in reversed(range(N)):
        K += ft.query(P[i] - 1)
        ft.update(P[i])
    K %= MOD
    
    # Compute sum over d of cnt[d] * pow2[N-1 -d]
    sum_terms = 0
    for d in range(1, N):
        cnt = 0
        for i in range(N - d):
            if P[i] > P[i + d]:
                cnt += 1
        term = cnt * pow2[N-1 - d]
        sum_terms = (sum_terms + term) % MOD
    
    ans = (K * pow2[N-1] - sum_terms) % MOD
    print(ans if ans >= 0 else ans + MOD)

if __name__ == "__main__":
    main()
0