N Cut N Eat

この解説では全体として0-indexedを用います。

操作で生成される $2N$ 個の乱数は順序のみが重要であり、また等しい値が生成される確率は $0$ としてよいため、生成される乱数を $(0,1,\dots ,2N-1)$ の順列 $(P_0,P_1,\dots ,P_{2N-1})$ に言い換え、$i$ 番目の操作では $x=\frac{P_{2i}}{2\pi},y=\frac{P_{2i+1}}{2\pi}$ とするとしても問題は本質的に等しくなります。また、言い換えた後の問題について条件を満たす $P$ の個数を $998244353$ で割った余りがそのままこの問題で出力すべき値となります。

条件を次のように言い換え、包除原理を行います。

• $0\leq i< 2N$ を満たす各整数 $i$ について、最終的な $S$ に $\frac{2i+1}{4\pi}$ が含まれる。

$2N$ 個の頂点からなり、$i$ 番目の条件に $(i,i+1)$ の辺が対応するようなグラフを考えます。(ただし、頂点番号は $\mathrm{mod}\ 2N$ で同一視します。)

ある条件を違反すると決め打った時、その条件に対応する辺が削除されます。

ここで、違反すると決め打った条件が一つでも存在する場合、このグラフのそれぞれの連結成分について、$P$ に次のような条件が課されます。

• $Q_{P_i} = i$ となるような $P$ の逆順列 $Q$ を考える。また、その連結成分に含まれる頂点の集合を $V$ とし、$R=\lbrace Q_x|x\in V \rbrace$ とする。この時、次の条件が成り立つ。
  • $x\in R$ ならば、$(x\oplus 1) \in R$。
• また、グラフの辺を $i\to i+1$ の向きの有向辺と考えた時、次の条件が成り立つ。
  • $x\in R$ かつ $x$ が偶数ならば、$Q_i=x$ となる頂点 $i$ から $Q_j=(x\oplus 1)$ となる頂点 $j$ へ到達できる。

違反すると決め打った条件が一つでも存在するような場合について、それぞれの連結成分の大きさを並べた数列 $(S_0,S_1,\dots ,S_{K-1})$ を考える動的計画法を行います。まず、あるグラフに対し $S$ を考えた場合、答えへの寄与は次のように計算できます。

• $S$ に奇数が含まれている場合、$0$
• そうでない場合、$S$ の各要素を $2$ で割った数列を $T$ とした時、${(-1)}^K \times \prod_{i=0}^{K-1}(\frac{S_i!}{2^{T_i}}) \times \frac{N!}{\prod_{i=0}^{K-1}(T_i!)}$

この式を動的計画法にすると、$S$ の末尾に $s=2t$ を追加する場合 $-\frac{s!}{2^{t}t!}$ を係数としてかけていくとすることで計算することができます。

また、ある $S$ に対応するグラフは複数個存在するため、最初または最後に追加する $s$ を係数としてかけるなどの方法でその部分の計算もすることができます。

この動的計画法を行うことで、この問題を $O(N^2)$ で解くことができました。違反する条件を一つも選ばない場合も別で計算することに注意してください。

(なお、この動的計画法は多項式の逆元を用いることで $O(N\log N)$ に高速化することができます。)