ARC228 A - Row and Col swap

考え方

同じ値 $i$ が $2$ つずつあると考えにくいので、まずはここを工夫する。

ある操作で、最終的に条件が満たされたとする。
このとき、$P$ 側にある $i$ を $+i$、$Q$ 側にある $i$ を $-i$ と書き換える。
そして操作を逆再生すると、与えられた $2$ つの順列に適切に符号がつけてあったことにできる。

このとき、異なる割り当てが同じ手順で両方条件を満たすようにはならない。
したがって、問題は以下のように言い換えられる。

PとQの同じ値の、片方は+、片方は-に置き換える。
問題にある操作をM回繰り返して、P側を全て+、Q側を全て-にする。
このような初期符号の割り当て方と手順は何通りあるか？

ということで、初期符号と手順の組 $2^N\times (N^2)^M$ 通り全ての検証をすればよい。
これは、前後半分けて動的計画法を $2$ つ行うことで達成できる。

DPテーブルは、同じ縦列の符号の組がいくつあるかごとに情報を持つ。
$[+-]$ という組が $i$ 組、$[-+]$ という組が $j$ 組あるとする。
$[++]$ と $[--]$ は同数あるので、残りの半分ずつある。
このような組数になっているパターン数を dp[i][j] とする。

前半の動的計画法

初期の符号割り当て $2^N$ 通りの分類を求める。

まず、$P$ と $Q$ を巡回順に並べなおす。
というのは、与えられた問題で $P_i$ と $P_j$ を、$Q_i$ と $Q_j$ を同時に入れ替えても影響がない。
よって、例えば以下のように、巡回順に並べなおす。

P : 1 2 3 4 5 6
Q : 5 6 2 4 1 3
↓
P : 1 5 2 6 3 4
Q : 5 1 6 3 2 4

すなわち、$(1,5),(2,6,3),(4)$ がそれぞれの中で $1$ つずつ右にずれる巡回になっているような状態にする。
そしてこの順番通りにDPを行うことで、持つ状態数を減らすことができる。

dp[i][j] は前述の通りの意味で、さらに次が $[+?]$ であるべきか $[-?]$ であるべきかで分けて数える。
巡回が続いている限り、$1$ つ前が $[?+]$ であれば次は $[-?]$ である必要がある、というのを利用する。

つまり、巡回の内部では、配るDPとして以下の $4$ つの遷移が成立する。

• dp[i][j][+] $\to$ dp[i][j][-] （$[++]$ にする場合）
• dp[i][j][-] $\to$ dp[i][j][+] （$[--]$ にする場合）
• dp[i][j][+] $\to$ dp[i+1][j][+] （$[+-]$ にする場合）
• dp[i][j][-] $\to$ dp[i][j+1][-] （$[-+]$ にする場合）

巡回の切れ目では、以下のように考える。

切れ目では、次に何が来るべきという指定がないので、全て「次が $[+?]$ であるべき」側で数えておく。
すると、自然と次の巡回が $[+?]$ で始まったものだけ数えることになる。
そして、巡回の最後の組では $4$ つのうち $[?-]$ に相当する $2$ つの遷移だけ行う。
結果として、設計通り dp[i][j][+] の方だけ値が構築され、dp[i][j][-] はすべて $0$ になる。

このとき、dp[i][j][+] に入っている個数は、最後の巡回が $[+?]$ で始まり $[?-]$ で終わるものだけ。
これに、最後の巡回が $[-?]$ で始まり $[?+]$ で終わるものの個数を加えなければならない。
実はこの個数は、全体の $+/-$ を入れ替えることを考えると、実は dp[j][i][+] に入っている。
よって、$i$ と $j$ を入れ替えた値同士、お互いをお互いに足せばよい。
（dp[i][i][+] は $2$ 倍することになる）

巡回順に並べなおしたのを見ながら $N$ 要素分繰り返す。
これで、初期の符号割り当て $2^N$ 通りの分類を求めることができた。

以後 [-] のデータは不要なので、[+] の方だけ取り出したものにDPテーブルを作り直す。

後半の動的計画法

後半では、このデータが操作 $1$ 回ごとにどう変わるか調べればよい。
操作する場所の選び方は $N(N-1)/2\times 2+N=N^2$ とおりある。
そのときの $i$ や $j$ の変化、つまり遷移先は以下のようになっている。

$[++]$ と $[--]$ はそれぞれ $k=(N-i-j)/2$ 組ある。

• $i,j$ がともに変わらないものは、$4(i+j)k+i(i-1)+j(j-1)+2k(k-1)+2k$ 通り
  • $[++]$ または $[--]$ と、$[+-]$ または $[-+]$ の同じ段同士の入れ替えが $4(i+j)k$ 通り
  • 同タイプ同士での同じ段同士の入れ替えが $i(i-1)+j(j-1)+2k(k-1)$ 通り
  • $[++]$ または $[--]$ での上下入れ替えが $2k$ 通り
• $[+-]$ と $[-+]$ の同じ段同士を入れ替えると、$i,j$ がともに $1$ 減る。これは $2ij$ 通り
• $[++]$ と $[--]$ の同じ段同士を入れ替えると、$i,j$ がともに $1$ 増える。これは $2k^2$ 通り
• $[+-]$ の上下を入れ替えると、$i$ が $1$ 減って $j$ が $1$ 増える。これは $i$ 通り
• $[-+]$ の上下を入れ替えると、$i$ が $1$ 増えて $j$ が $1$ 減る。これは $j$ 通り

この遷移を愚直に $M$ 回実行すればよい。

最終的に、$N$ 組全てが $[+-]$ になっている個数が答えとなる。

計算量

計算量は、前半が $O(N^3)$、後半が $O(MN^2)$ である。
メモリも計算量も余裕がないので、明らかにデータがない場所の処理をスキップするなど工夫すること。
C++ならそこまでせずとも一応通りそうではあるが。

入力例1での動作

入力を受け取る。

n: 3
m: 1
p: {1, 2, 3}
q: {1, 3, 2}

まず、各位置にある $P$ 側の値から $Q$ 側の値への対応を見ると、$1\to1,2\to3,3\to2$ となる。
したがって、巡回は $(1),(2,3)$ の $2$ 個である。

前半のDPを行う。
最初の巡回 $(1)$ を処理し終えると、値 $1$ の符号の付け方は $[+-]$ と $[-+]$ の $2$ 通りである。
DPは次のようになる。

dp[1][0][+] = 1
dp[0][1][+] = 1

次に巡回 $(2,3)$ を処理する。
最初の $2$ を処理した時点で、DPは次のようになる。

dp[1][0][-] = 1
dp[2][0][+] = 1
dp[0][1][-] = 1
dp[1][1][+] = 1

最後の $3$ を処理して巡回を閉じ、さらに $+/-$ を全て反転した場合も加える。
前半DPの最終状態は次のようになる。

dp[3][0] = 1
dp[2][1] = 1
dp[1][2] = 1
dp[0][3] = 1
dp[1][0] = 2
dp[0][1] = 2

合計は $1+1+1+1+2+2=8=2^3$ で、全ての初期符号割り当てが分類されている。

後半では、この状態から操作を $M=1$ 回行う。
$N=3$ なので、各状態から選べる操作は $N^2=9$ 通りである。
遷移後のDPは次のようになる。

dp[3][0] = 7
dp[2][1] = 11
dp[1][2] = 11
dp[0][3] = 7
dp[1][0] = 18
dp[0][1] = 18

合計は $72=8\times9$ で、$8$ 通りの初期符号割り当てそれぞれについて $9$ 通りの操作を全て数えられている。

最終的に $P$ 側を全て $+$、$Q$ 側を全て $-$ にするには、全 $3$ 組が $[+-]$ であればよい。
よって答えは dp[3][0] の値である $7$ となる。

注意点

答えは $998244353$ で割った余りを要求されているので、剰余類環の考えに従って処理する。
何か足し算や掛け算をするたびに結果を % 998244353 する。
計算量削減のために剰余を取る回数を減らしてもいいが、long long 型から溢れない程度にすること。

別解

特になし。