AtCoder Regular Contest++ 228 A,B,C問題メモ

AtCoder Regular Contest++ 228

A - Row and Col swap

• $(1,2,\dots,N)$ の順列 $P=(P_1,P_2,\dots,P_N),Q=(Q_1,Q_2,\dots,Q_N)$ が与えられます。
• $P,Q$ に対して、以下の操作のいずれか一つを選び行うことを $M$ 回繰り返します。
  • $1 \le i \lt j \le N$ を満たす整数 $i,j$ を選び、$P_i,P_j$ を入れ替える。
  • $1 \le i \lt j \le N$ を満たす整数 $i,j$ を選び、$Q_i,Q_j$ を入れ替える。
  • $1 \le i \le N$ を満たす整数 $i$ を選び、$P_i,Q_i$ を入れ替える。
• $M$ 回の操作終了後に $P,Q$ がいずれも $(1,2,\dots,N)$ の順列になるような操作列の個数を $998244353$ で割った余りを求めてください。

• $1 \le N,M \le 500$
• $P,Q$ は $(1,2,\dots,N)$ の順列
• 入力される値は全て整数

第1問目ではあるが、個人的な体感では同点数のB問題どころか、より点数の高いC問題より難しいと感じた。 取っかかりの発想、数えたいものをきちんと数え上げるためのDPの実装方法、実装の複雑さあたりがいずれもハイレベル。

まず、いくらか操作を施した途中の $P$ と $Q$ の状態は、以下の $(a,b,c,d)$ で管理できる。

• $P$ と $Q$ に1つずつある各値につき、2つのうち最終的にどちらが $P$ 側に属するか、というのを決め打つ。
  • $P$ 側に属する方を $0$、$Q$ 側に属する方を $1$ とする。
• 各 $i$ に対し、$(P_i,Q_i)$ が $(0,0),(0,1),(1,0),(1,1)$ のいずれかになる。
  • $a$ を「$(P_i,Q_i)=(0,0)$ となるような $i$ の個数」とする。
  • $b:(0,1),c:(1,0),d:(1,1)$ で同様に定義する。
• 1回の操作では、これらが高々 $\pm 1$ だけ増減するのみ。操作の個数も $a～d$ で表せる。
• 最終的に $b=N,a=c=d=0$ となったら成功。
  • そうなるような操作手順の個数が、最初の決め打ち方を実現できる操作手順の個数である。

ここで、全体で $0,1$ の個数は $N$ 個ずつなので、$a=d$ が常に成り立つ。
さらに、$c=N-a-b-d$ であることを考えると、状態は $(a,b)$ だけ持っておけば十分である。

P  3  1  4  5  2  →  0  0  1  1  0
Q  5  2  4  1  3      0  1  0  1  1  と割り当てたとすると、操作によって

                      0  0  0  0  0
                      1  1  1  1  1  となった状態は、必ず P も Q も順列になっている。

2段階のDPをする。

• ①最初の $P,Q$ から、実現可能な決め打ち方を全て求める
  • $\mathrm{X}[a,b]:=(0,0)$ が $a$ 個、$(0,1)$ が $b$ 個となるような最初の決め打ち方の数
• ②$X$ をそのまま初期状態として、操作手順の個数を数える。
  • $\mathrm{Y}[a,b]:=(0,0)$ が $a$ 個、$(0,1)$ が $b$ 個となるような（最初の決め打ち方×操作手順）の数

$M$ 回、②を遷移させた後の $Y[0,N]$ の値が最終的な答えとなる。

$X[a,b]$ を求めたい。

$P$ 側で例えば要素 $3$ を $0$（最終的に $P$ に属する）と決めると、$Q$ 側の $3$ には $1$ を割り振らないといけない。
だが当然、全ての割り振り方 $2^N$ 通りそれぞれで $a,b$ を数えるわけにはいかない。

$Q_i→P_j$ が同じ値となるように追っていけば、順列のようにサイクルができる。

■入力例3を並べ替えたもの
P  6  1  8  4  3  5  2  7   6→1→8→4 という長さ4のサイクルが1つ
    ↗ ↗ ↗    ↗    ↗    3→5, 2→7 という長さ2のサイクルが2つ
Q  1  8  4  6  5  3  7  2

このように、サイクルが続く限り $Q_i=P_{i+1}$ となるように、$(P_i,Q_i)$ セットで各要素を並べ替える。 こうしても可能な操作、ひいては答えには影響ない。

この時、属するサイクルが異なる要素間では、$0,1$ の割り当て方は互いに影響しない。 同じサイクルで隣接する $Q_i$ と $P_{i+1}$、および始端と終端（$P_1=6$ と $Q_4=6$ とか）で、割り当てる値が一方は $0$ で一方が $1$ という制約が発生する。

いきなり複数サイクルを連結したDPは難しいので、 まずは1つのサイクルで $X[a,b]$ の算出を考える。

以下のDPができる。ただし、サイクル長を $L$ とし $Q_{0}=Q_{L}$ とする。

• $\mathrm{DP}[i,s,p,a,b]:=$
  • $Q_i$ までの割り当てを決め（必然的に $P_{i+1}$ の割り当ても決まる）
  • $Q_{0}$ の割り当てを $s=0/1$ と決め、
  • $Q_{i}$ の割り当てを $p=0/1$ と決め、
  • $i$ までで $(0,0)$ が $a$ 個、$(0,1)$ が $b$ 個となるような割り当て方の個数
• 初期化
  • $\mathrm{DP}[0,0,0,0,0]=\mathrm{DP}[0,1,1,0,0]=1$
  • $Q_{0}$ に $0,1$ をそれぞれ割り当てる場合を想定

$i=1,2,...,L-1$ に対して、$Q_i$ に $0/1$ のいずれを置くかで、 $p$ の情報と合わせて $(0,0),(0,1)$ が発生するかどうかが決まる。 発生したら $a,b$ に反映させながらDPしていく。

サイクルの最後 $i=L$ では、遷移が少し異なる。 $s$ によって $Q_L$ への割り当てが既に決定しているので、自動的に $(P_L,Q_L)$ が $(0,0),(0,1)$ となるかどうか決まる。
また、サイクルが終了したら $s,p$ の情報は不要になるので、$a,b$ が同じもの同士で総和を取ってまとめる。
このサイクル末端の特殊処理を「閉じる処理」とする。

これで、1サイクルのDPができた。

続けてこの結果を初期値としつつ次のサイクルを開始する。 直前のサイクルで閉じる処理によって $(a,b)$ 毎にまとめ上げた値を $X'[a,b]$ として、

• $\mathrm{DP}[i,0,0,a,b]=\mathrm{DP}[i,1,1,a,b]=X'[a,b]$

とすればよい。 その後、同様に遷移を $サイクル長-1$ 回おこない、最後に閉じる処理をする、ということを繰り返す。

以上で、$O(N^3)$ で $X[a,b]$ が求められた。

$X[a,b]$ を引き継ぐ。

• $\mathrm{DP}[i,a,b]:=i$ 回目の操作の後、$(0,0)$ が $a$ 個、$(0,1)$ が $b$ 個となるような（最初の決め打ち方×操作手順）の数
• 初期化
  • 各 $a,b$ につき、$\mathrm{DP}[0,a,b]=X[a,b]$

$(P_i,Q_i)$ が $(0,0)～(1,1)$ の各場合において、各操作が「$a,b$ にどのような変化をもたらすか」と「何通りの操作箇所があるか」を考えていく。

例えば、$(P_i,Q_i)=(0,0)$ と $(P_j,Q_j)=(0,1)$ である箇所が選ばれた場合、 $P$ 側を入れ替えようが、$Q$ 側を入れ替えようが、操作後で「$(0,0)$ が1個と $(0,1)$ が1個」という状態は維持される。
この時、$i,j$ の選び方と、$P,Q$ のどちらに対して入れ替えるかで、$2ab$ 通りの操作がある。

別の例では、$(P_i,Q_i)=(0,0),(P_j,Q_j)=(1,1)$ に対する操作は、$P,Q$ いずれを入れ替えても $(0,1),(1,0)$ が1個ずつという状態になる。

場合分けは多いものの、丁寧に考えれば素直なDPで遷移を書ける。

$M$ 回の遷移後、$\mathrm{DP}[M,0,N]$ が答えとなる。計算量は $O(N^2M)$

Python3

def solve(n, m, ppp, qqq):
    MOD = 998244353

    pqs = [(p - 1, q - 1) for p, q in zip(ppp, qqq)]
    pqs.sort()
    qqq = [pq[1] for pq in pqs]

    checked = [False] * n
    cycle_lengths = []
    for i in range(n):
        if checked[i]:
            continue
        checked[i] = True
        res = 1
        s = i
        while qqq[i] != s:
            i = qqq[i]
            checked[i] = True
            res += 1
        cycle_lengths.append(res)

    dp = [[[[0] * (n + 1) for _ in range(n // 2 + 1)] for _ in range(2)] for _ in range(2)]
    # 閉じてる状態: dp[0][0][c00][c01] = dp[1][1][c00][c01]
    # 開いてる状態: dp[現サイクルの先頭0/1][直前0/1][c00][c01]
    dp[0][0][0][0] = dp[1][1][0][0] = 1
    acc = 0
    for l in cycle_lengths:
        for i in range(1, l):
            for s in (0, 1):
                for c00 in range((acc + i + 1) // 2, -1, -1):
                    for c01 in range(acc + i, -1, -1):
                        # 前0,今0→10, 前0,今1→11, 前1,今0→00, 前1,今1→01
                        v0 = v1 = dp[s][0][c00][c01]
                        if c00 > 0:
                            v0 += dp[s][1][c00 - 1][c01]
                            v0 %= MOD
                        if c01 > 0:
                            v1 += dp[s][1][c00][c01 - 1]
                            v1 %= MOD
                        dp[s][0][c00][c01] = v0
                        dp[s][1][c00][c01] = v1
        acc += l
        for c00 in range(acc // 2, -1, -1):
            for c01 in range(acc, -1, -1):
                v = dp[0][0][c00][c01] + dp[1][0][c00][c01]
                if c00 > 0:
                    v += dp[0][1][c00 - 1][c01]
                if c01 > 0:
                    v += dp[1][1][c00][c01 - 1]
                v %= MOD
                dp[0][0][c00][c01] = dp[1][1][c00][c01] = v
                dp[0][1][c00][c01] = dp[1][0][c00][c01] = 0

    dp = dp[0][0]
    for _ in range(m):
        ndp = [[0] * (n + 1) for _ in range(n // 2 + 1)]
        for c00 in range(n // 2 + 1):
            c11 = c00
            for c01 in range(n - c00 * 2 + 1):
                c10 = n - c00 * 2 - c01
                base = dp[c00][c01]
                # (00&00, 00&01, 00&10, 01&01, 01&11, 10&10, 10&11, 11&11)x2, 00内, 11内 の交換→不変
                type1 = c00 * (c00 - 1)
                type1 += c01 * (c01 - 1)
                type1 += c10 * (c10 - 1)
                type1 += c11 * (c11 - 1)
                type1 += c00 * (c01 + c10) * 2
                type1 += c11 * (c01 + c10) * 2
                type1 += c00 + c11
                ndp[c00][c01] += base * type1
                ndp[c00][c01] %= MOD
                # 00&11→01&10
                if c00 > 0:
                    ndp[c00 - 1][c01 + 1] += base * c00 * c11 * 2
                    ndp[c00 - 1][c01 + 1] %= MOD
                # 01&10→00&11
                if c01 > 0 and c10 > 0:
                    ndp[c00 + 1][c01 - 1] += base * c01 * c10 * 2
                    ndp[c00 + 1][c01 - 1] %= MOD
                # 01内→10
                if c01 > 0:
                    ndp[c00][c01 - 1] += base * c01
                    ndp[c00][c01 - 1] %= MOD
                # 10内→01
                if c10 > 0:
                    ndp[c00][c01 + 1] += base * c10
                    ndp[c00][c01 + 1] %= MOD
        dp = ndp

    ans = dp[0][n]
    return ans


n, m = list(map(int, input().split()))
ppp = list(map(int, input().split()))
qqq = list(map(int, input().split()))
ans = solve(n, m, ppp, qqq)
print(ans)

B - Minimize Topological Order

• $(1,2,\dots,N)$ の順列 $P=(P_1,P_2,\dots,P_N)$ と長さ $N$ の正整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。
• 頂点に $1$ から $N$ の番号が付いた $N$ 頂点の根付き木 $T$ に対して、以下で $f(T)$ を定義します。
  • $(1,2,\dots,N)$ の順列 $Q=(Q_1,Q_2,\dots,Q_N)$ のうち、以下の条件を満たすものを良い順列と呼ぶ。
    • 根以外の全ての頂点 $v$ に対して、$v$ の親を頂点 $u$ とした時、$Q$ において $u$ は $v$ より前に現れる。
  • 良い順列のうち、辞書順最小のものを $f(T)$ とする。
• また、$N$ 頂点の根付き木 $T$ のコストを $\sum_{i=1}^{N} A_i c_i^2$ と定義します。ここで、$c_i$ は $T$ における頂点 $i$ の子の個数です。
• $N$ 頂点の根付き木 $T$ のうち $f(T) = P$ を満たすものに対する $T$ のコストの最小値を求めてください。

• $1 \le N \le 2 \times 10^5$
• $P$ は $(1,2,\dots,N)$ の順列
• $1 \le A_i \le 10^6$
• 入力される値は全て整数

木 $T$ から「良い順列」を構築するには、以下のようになる。

• 根付き木を、根付き森として解釈する。（根が複数あってもいいとする）
• 数列 $Q$ を空で初期化する。
• 以下を $N$ 回繰り返す。
  • 現在の根を1つ選ぶ。$v$ を選んだとして、$v$ を $Q$ の末尾に追加する。
  • 頂点 $v$ を削除し、$v$ の子を根とした部分木をそれぞれ新たな木とする。

これが $f(T)$、つまり辞書順最小になるためには、$v$ を選ぶときに、その時点で最も小さい番号のものを選ぶとよい。

以上を踏まえて、$P$ が決まっているときに $f(T)=P$ となるような木 $T$ を考える。

例えば、$P=(...,9,7,...)$ のように、$P_{i-1} \gt P_i$ であるような $P_i$ は、$P_{i-1}$ を親とするしかない。

• $9$ が根として選ばれた時点では、$7$ は選べる状態ではなかった。
  • 選べる状態なら $9$ より先に選ばれてないといけない。
• $9$ が削除されることで、はじめて $7$ が選べるようになった。
• → $7$ の親は $9$ でないと矛盾

では、$P=(...,9,6,2,7,...)$ みたいな場合は？

$7$ は、$9$ より前の頂点を親にはできない。$9$ を選ぶ時点で選択可能であってはいけないので。 一方、$9$ が親の場合はOK。$9$ が $6,7$ を子として持っていた場合、$6$ の方が優先して選ばれるので、矛盾しない。 また、$6$ や $2$ が親であっても特に矛盾しない。

よって、各 $P_i$（$i \ge 2$）は、以下のように親を選択できる。

• $i$ より左で、$P_i$ より大きい直近の値を $P_{L_i}$ とする。ただし、存在しない場合、$L_i=1$ とする。
• $P_{L_i},P_{L_i+1},...,P_{i-1}$ の範囲の頂点から親を選択できる。

このように構築した木は、全て $f(T)=P$ を満たす。この中で最小コストを求めたい。

以下の貪欲が成り立つ。

• 各 $P_i$（$i \ge 2$）につき、親とできる頂点の中で、その時点で子を1つ増やすときのコストの増分が最も小さい頂点を親とする。

同じコストの頂点が複数ある場合、どれを選んでもよい。

貪欲解の正当性

$L_i$ は stack を使うことで求められる。

コストは、$i=2,...,N$ に対して $P_{L_i},P_{L_i+1},...,P_{i-1}$ における「次に子を加えたときのコスト増分」の最小値が欲しいので、$P$ の出現順にセグ木を構築し、（コスト増分, $i$, 子の個数）などを載せ、1点更新・区間最小値取得ができればよい。

Python3

from atcoder.segtree import SegTree


def solve(n, ppp, aaa):
    ppp = [p - 1 for p in ppp]

    # left[i]: iより左で ppp[i] より大きい直近の値の位置(無ければ0)
    left = [0] * n
    stack = []
    for i, p in enumerate(ppp):
        while stack and ppp[stack[-1]] <= p:
            stack.pop()
        if stack:
            left[i] = stack[-1]
        stack.append(i)

    INF = 1 << 60
    init = [(aaa[p], i, 1) for i, p in enumerate(ppp)]
    sgt = SegTree(min, (INF, INF, 1), init)
    # (次の子を付けた場合のコスト, index, 次の子が何番目か)
    ans = 0
    for i in range(1, n):
        l = left[i]
        cost, j, count = sgt.prod(l, i)
        ans += cost
        count += 1
        new_cost = aaa[ppp[j]] * (count * 2 - 1)
        sgt.set(j, (new_cost, j, count))
    return ans


n = int(input())
ppp = list(map(int, input().split()))
aaa = list(map(int, input().split()))
ans = solve(n, ppp, aaa)
print(ans)

C - Partially Sort

• $(1,2,\dots,N)$ の順列 $P=(P_1,P_2,\dots,P_N)$ が与えられます。
• $(1,2,\dots,N)$ の部分列 $x=(x_1,x_2,\dots,x_k)$ に対して、以下の手続きによって得られる数列を $f(x)$ と置きます。
  • 数列 $Q=(Q_1,Q_2,\dots,Q_N)$ を $Q = P$ で初期化する。
  • $(Q_{x_1},Q_{x_2},\dots,Q_{x_k})$ を昇順に並び替えて得られる数列を $A=(A_1,A_2,\dots,A_k)$ と置く。
  • $1 \le i \le k$ を満たす整数 $i$ に対して、$Q_{x_i}$ を $A_i$ で置き換える。この時点での $Q$ を $f(x)$ とする。
• $x$ として考えられるものは空列も含めて $2^N$ 通りありますが、その全てに対する $f(x)$ の転倒数の総和を $998244353$ で割った余りを求めてください。

• $2 \le N \le 2 \times 10^5$
• $P$ は $(1,2,\dots,N)$ の順列
• 入力される値は全て整数

序盤の取っかかりは見えやすいが、中盤からの式変形がヘビー。

転倒数の期待値を考え、最後に $2^N$ 倍することにする。

転倒数の期待値は、「全てのペアにおける、操作後に転倒している確率」を足し合わせると求めることができる。

まず、値の各ペアについて、互いに選ばれたり、互いに選ばれない場合を考える。

P で転倒してないペア
... 10 ... 20 ...

P で転倒してるペア
... 20 ... 10 ...

転倒してないのは、「互いに選ばれる」「互いに選ばれない」のいずれも、$f(x)$ では転倒しない。
転倒してるのは、「互いに選ばれる」と転倒せず、「互いに選ばれない」なら転倒する。

それぞれは $1/4$ で発生するので、まとめると「初期状態の $P$ の転倒数 $\times \frac{1}{4}$」が期待値に寄与する。

「一方が選ばれ、一方が選ばれない」場合は、どちらが選ばれるかとか、最初に転倒してたかどうかとか、 場合分けで寄与が異なり、ペアを主体に考えると上手くまとめ上げるのが難しく、$O(N^2)$ から落ちない。

「選ばれない方」を固定した時、 他の要素のうち「選ばれ、ソートされることで転倒が発生するような要素の個数期待値」を求める。

$i$ が選ばれないとして、$j \in x$ のうち、以下が発生する個数だけ転倒数に寄与する。

• (1) ソート後に $i$ より左（$j \lt i$）に来て、$P_i$ より大きい（$P_j \gt P_i$）ような $j$
• (2) ソート後に $i$ より右（$i \lt j$）に来て、$P_i$ より小さい（$P_i \gt P_j$）ような $j$

重要な点として、この2種類は同時に発生することはない。

(1)と(2)は同時には発生しない
                             i(固定)
       P   2  7  4  9  3 13  8 12  6  5 10 11  1

 xの一例      *     *  *  *        *     *
ソート後      3     6  7  9       10    13          (1)に該当するのが1個(9)
                          ~
 xの一例   *        *              *  *        *
ソート後   1        2              5  6        9    (2)に該当するのが2個(5,6)
                                   ~  ~

ここで、以下を定義する。

• $L_i:=$ 初期状態の $P$ で、$i$ より左で $i$ より大きい要素数
• $R_i:=$ 初期状態の $P$ で、$i$ より右で $i$ より小さい要素数
  • ※この値は、$x$ に選ばれたか選ばれないかに関わらない固定値。
  • 転倒数を求めるのと同じ要領で $O(N \log{N})$ で算出可能。

このうち、左から $l$ 個、右から $r$ 個が選ばれたとすると、 ソートにより $l$ 個は左→右に、$r$ 個は右→左に、交換するように移動する。

• $l \gt r$ の時は、$r$ 個が移動することで空いた右側スペースに $l$ 個が収まりきらないので、$l-r$ 個の(1)が発生する。
• $l \lt r$ の時は、$l$ 個が移動することで空いた左側スペースに $r$ 個が収まりきらないので、$r-l$ 個の(2)が発生する。

よって、$i$ を選ばれない要素として固定した時の、選ばれる要素との転倒の個数期待値は、

• $\displaystyle \frac{\sum_{l=0}^{L_i}\sum_{r=0}^{R_i}|l-r|\binom{L_i}{l}\binom{R_i}{r}}{2^{L_i+R_i}}$

と表せる。このままではまだ $O(N^2)$ なので、二重ループの分子をなんとかしたい。
この形は、以下のように変形できる。ただし、$\displaystyle S(n,r):=\sum_{k=0}^{r}\binom{n}{k}$ とする。

• $\displaystyle \sum_{l=0}^{L_i}\sum_{r=0}^{R_i}|l-r|\binom{L_i}{l}\binom{R_i}{r}=2^{L_i+R_i-1}(L_i-R_i)+2 (R_i \cdot S(L_i+R_i,R_i-1) - (L_i+R_i) \cdot S(L_i+R_i-1,R_i-2))$

導出は、$\dbinom{R_i}{r}=\dbinom{R_i}{R_i-r}$ を利用して式変形後、絶対値が厄介なので外す。

• $\displaystyle \sum_{l=0}^{L_i}\sum_{r=0}^{R_i}|l-r|\binom{L_i}{l}\binom{R_i}{r}=\sum_{l=0}^{L_i}\sum_{r=0}^{R_i}|l+r-R_i|\binom{L_i}{l}\binom{R_i}{r}$
• $\displaystyle =\sum_{l=0}^{L_i}\sum_{r=0}^{R_i}(l+r-R_i)\binom{L_i}{l}\binom{R_i}{r}+(E:絶対値を外した影響の調整項)$
• $\displaystyle =\sum_{l=0}^{L_i}\sum_{r=0}^{R_i}(l+r)\binom{L_i}{l}\binom{R_i}{r}-R_i\sum_{l=0}^{L_i}\binom{L_i}{l}\sum_{r=0}^{R_i}\binom{R_i}{r}+E$

すると、$l+r$ が一定のものでヴァンデルモンドの畳み込みが適用できるので、

• $\displaystyle =\sum_{k=0}^{L_i+R_i} k \binom{L_i+R_i}{k} - R_i \cdot 2^{L_i+R_i} + E$
• $\displaystyle =(L_i+R_i)\sum_{k=1}^{L_i+R_i} \binom{L_i+R_i-1}{k-1} - R_i \cdot 2^{L_i+R_i} + E$
• $=(L_i+R_i) \cdot 2^{L_i+R_i-1} - R_i \cdot 2^{L_i+R_i} + E$
• $=(L_i-R_i) \cdot 2^{L_i+R_i-1} + E$

となる。

あとは $E$ だが、$l+r \lt R_i$ のものを、本来絶対値で正負反転すべきところを負のまま足してしまっているのを補正する。 ここにも畳み込みが適用できるので、

• $\displaystyle E=2\sum_{s \lt R_i}(R_i-s)\binom{L_i+R_i}{s}$
• $\displaystyle =2(R_i\sum_{s \lt R_i}\binom{L_i+R_i}{s} - \sum_{s \lt R_i}s \cdot \binom{L_i+R_i}{s})$
• $\displaystyle =2(R_i\sum_{s \lt R_i}\binom{L_i+R_i}{s} - (L_i+R_i)\sum_{s \lt R_i} \binom{L_i+R_i-1}{s-1})$
• $\displaystyle =2(R_i \cdot S(L_i+R_i,R_i-1) - (L_i+R_i) \cdot S(L_i+R_i-1,R_i-2))$

よって、2種類の二項係数のprefixの和に変換できた。

$S(n,r)$ は効率的に一発で求める方法がないが、 隣接1マス（$S(n-1,r)$ や $S(n,r+1)$ など）に遷移する計算は $O(1)$ で可能。
また、全体を通して必要となる $S(*,*)$ は高々 $2N$ 個なので、 Mo's Algorithm を使えば $O(N \sqrt{N})$ で全て計算できる。

その結果に適当な係数をかけて合計すれば、全体の答えが求められる。

Python3

from atcoder.fenwicktree import FenwickTree


def precompute_factorials(n, MOD):
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f = f * m % MOD
        factorials.append(f)
    f = pow(f, MOD - 2, MOD)
    finvs = [1] * (n + 1)
    finvs[n] = f
    for m in range(n, 1, -1):
        f = f * m % MOD
        finvs[m - 1] = f
    return factorials, finvs


class BinomialPrefixSumMo:
    """二項係数の prefix 和 S(n, r) = Σ_{i=0}^{r} C(n, i) mod p をクエリ処理するクラス。

    閉じた形はないが、隣接する (n, r) への遷移は O(1) でできる:
        S(n, r+1) = S(n, r) + C(n, r+1)
        S(n, r-1) = S(n, r) - C(n, r)
        S(n+1, r) = 2*S(n, r) - C(n, r)      (パスカルの規則)
        S(n-1, r) = (S(n, r) + C(n-1, r)) / 2
    クエリをまとめて Mo's algorithm の順に処理すると総移動量 O((max_n + Q) * sqrt(max_n))。

    ncr には範囲外 (n < 0, r < 0, n < r) で 0 を返す関数を渡すこと。
    n <= max_n に収めるのは呼び出し側の責務(超えたら ValueError)。
    """

    def __init__(self, ncr, max_n, mod=998244353):
        self.ncr = ncr
        self.max_n = max_n
        self.mod = mod
        self.inv2 = pow(2, mod - 2, mod)
        self.n = 0
        self.r = 0
        self.val = 1  # S(0, 0) = C(0, 0)

    def next(self, i, j):
        """現在位置から (i, j) まで隣接遷移で移動し、S(i, j) を返す。

        0 <= i <= max_n を想定(j は任意。範囲外の j でも値は正しいが、移動量が
        無駄なので呼び出し側で [-1, i] にクランプ推奨)。移動量はマンハッタン距離に比例。
        """
        if not 0 <= i <= self.max_n:
            raise ValueError(f'n={i} is out of range [0, {self.max_n}]')
        ncr = self.ncr
        mod = self.mod
        inv2 = self.inv2
        n, r, cur = self.n, self.r, self.val
        while n < i:
            cur = (2 * cur - ncr(n, r)) % mod
            n += 1
        while n > i:
            n -= 1
            cur = (cur + ncr(n, r)) * inv2 % mod
        while r < j:
            r += 1
            cur = (cur + ncr(n, r)) % mod
        while r > j:
            cur = (cur - ncr(n, r)) % mod
            r -= 1
        self.n, self.r, self.val = n, r, cur
        return cur

    def queries(self, qs):
        """qs = [(i, j), ...] に対する S(i, j) を、Mo's に適した順に求めてから元の順で返す。

        j は値を変えずに [-1, i] へクランプして移動量を抑える
        (S(i, j<0) = 0, S(i, j>=i) = 2^i = S(i, i))。
        """
        q = len(qs)
        if q == 0:
            return []
        norm = [(i, min(max(j, -1), i)) for i, j in qs]
        block = max(1, int(self.max_n / q ** 0.5))

        def key(k):
            i, j = norm[k]
            b = i // block
            return b, j if b % 2 == 0 else -j  # 奇数ブロックは r 降順(snake)

        ans = [0] * q
        for k in sorted(range(q), key=key):
            ans[k] = self.next(*norm[k])
        return ans


def solve(n, ppp):
    MOD = 998244353

    INV2 = pow(2, -1, MOD)
    POW2s = [1]
    INV2s = [1]
    for _ in range(n):
        POW2s.append(POW2s[-1] * 2 % MOD)
        INV2s.append(INV2s[-1] * INV2 % MOD)

    facts, finvs = precompute_factorials(n, MOD)

    def ncr(n, r):
        if n < 0 or r < 0 or n < r:
            return 0
        return facts[n] * finvs[r] % MOD * finvs[n - r] % MOD

    ppp = [p - 1 for p in ppp]
    prefix_sum_queries = []  # (n, r)
    prefix_sum_coefficients = []
    fwt = FenwickTree(n)
    inv = 0
    exp = 0
    for i in range(n):
        p = ppp[i]
        ll = fwt.sum(0, p)
        fwt.add(p, 1)
        l = i - ll  # i より左で Pi より大
        r = p - ll  # i より右で Pi より小
        if l + r == 0:
            continue
        inv += l
        exp += l - r
        if r >= 1:
            prefix_sum_queries.append((l + r, r - 1))
            prefix_sum_coefficients.append(r * INV2s[l + r - 1] % MOD)
        if r >= 2:
            prefix_sum_queries.append((l + r - 1, r - 2))
            prefix_sum_coefficients.append(-(l + r) * INV2s[l + r - 1] % MOD)

    bps = BinomialPrefixSumMo(ncr, n, MOD)
    result = bps.queries(prefix_sum_queries)
    ans = (inv + exp) * POW2s[n - 2] % MOD
    tmp = 0
    for r, c in zip(result, prefix_sum_coefficients):
        tmp += r * c
        tmp %= MOD
    ans += tmp * POW2s[n - 1]
    ans %= MOD
    return ans


n = int(input())
ppp = list(map(int, input().split()))
ans = solve(n, ppp)
print(ans)