ABC463 F - Senshuraku

考え方

最後の $N$ 試合の前での最大勝利数を $W$ とする。

最後の試合で各選手が増やせる勝利数は高々 $1$ なので、最終的な最多勝利数は $W$ または $W+1$ である。
そのため、現在の勝利数が $W-2$ 以下の選手は優勝できない。

そこで、選手を次の $3$ 種類に分類する。

• t: 現在の勝利数が $W$ の選手
• s: 現在の勝利数が $W-1$ の選手
• o: 現在の勝利数が $W-2$ 以下の選手

o の選手自身は既に優勝の可能性が存在しない。

最後の試合を、出場する選手の種類の組によって分類する。

• tt: t 同士の試合
• ts: t と s の試合
• ss: s 同士の試合
• to: t と o の試合
• so: s と o の試合

o 同士の試合は、誰が勝っても優勝争いに関係しないので処理の必要はない。

それぞれの種類の試合に出ている選手は、同じ立場なら同じ優勝確率になる。
そのため、次の $6$ 種類の優勝確率をそれぞれ計算し、出力は後でまとめて生成すればよい。

• ptt: tt の選手
• pts: ts の t 側の選手
• pst: ts の s 側の選手
• pss: ss の選手
• pto: to の t 側の選手
• pso: so の s 側の選手

まず、tt、ts、ss、to、so の個数を数える。
同時に、各選手が上の $6$ 種類のどれに属するかを、どこかに記録しておく。

次に、それぞれの種類の選手について、優勝確率を計算する。
これは、最終的な最多勝利数が $W+1$ の場合と $W$ の場合に分けて考えることになる。

最終的な最多勝利数が $W+1$ になるには、t の選手が最後の試合に勝つ必要がある。
tt の試合からは必ず $W+1$ の選手が $1$ 人生まれる。
また、ts と to の試合では、t 側が勝った試合だけ $W+1$ の選手が生まれる。

逆に、最終的な最多勝利数が $W$ になるには、$W+1$ の選手が生まれてはいけない。
つまり、tt の試合が存在せず、かつ ts と to の試合ではすべて t 側が負ける必要がある。
このとき、ts の試合からは $2$ 人、to からは t 側の $1$ 人、ss からは勝った $1$ 人が優勝候補者になる。
さらに、so の試合では s 側が勝った試合だけ $W$ の優勝候補者が $1$ 人増える。

ptt

ptt は、tt の選手の優勝確率である。

tt の選手が優勝するには、自分の最後の試合に勝って勝利数 $W+1$ になる必要がある。
自分が勝つ確率は $\frac{1}{2}$ である。

ts+to 個の試合のうち、t 側が勝つ試合数が $i$ 個であるとする。
このような結果は ${}_{\mathrm{ts}+\mathrm{to}}\mathrm{C}_{i}$ 通りある。

このとき、$W+1$ の優勝候補者は、tt の各試合の勝者と、ts・to のうち t 側が勝った選手。
合計で $\mathrm{tt}+i$ 人である。
よって、その中からこの選手が優勝者として選ばれる確率は $\frac{1}{\mathrm{tt}+i}$ である。

したがって、ptt は次のように計算できる。

$$
\sum_{i=0}^{\mathrm{ts}+\mathrm{to}}
\frac{1}{\mathrm{tt}+i}
\times
{}_{\mathrm{ts}+\mathrm{to}}\mathrm{C}_{i}
\times
\left(\frac{1}{2}\right)^{\mathrm{ts}+\mathrm{to}+1}
$$

ただし、tt=0 のとき、ptt を使う選手はいないので、計算を省略して ptt=0 とする。
以下の確率も同様に、該当者がなければスキップし、ゼロ除算の発生を防ぐものとする。

pts

pts は、ts の t 側の選手の優勝確率である。

まず、自分が最後の試合に勝つ場合を考える。
この場合、自分は勝利数 $W+1$ になり、優勝候補者になる。

ts+to 個の試合のうち、t 側が勝つ試合数が $i$ 個であるとする。
ただし、自分はその $i$ 人に含まれる必要がある。
そのため、試合の組は、残りの ts+to-1 個の試合から $i-1$ 個を選ぶことになる。

このとき、$W+1$ の優勝候補者は $\mathrm{tt}+i$ 人である。
よって、自分が勝つ場合の寄与は次のようになる。

$$
\sum_{i=1}^{\mathrm{ts}+\mathrm{to}}
\frac{1}{\mathrm{tt}+i}
\times
{}_{\mathrm{ts}+\mathrm{to}-1}\mathrm{C}_{i-1}
\times
\left(\frac{1}{2}\right)^{\mathrm{ts}+\mathrm{to}}
$$

次に、自分が最後の試合に負ける場合を考える。
この場合、自分の勝利数は $W$ のままである。
したがって、tt=0 であり、さらに ts と to の試合ではすべて t 側が負ける必要がある。

この条件のもとで、so の試合のうち s 側が勝つ試合数を $i$ 個とする。
このような結果は ${}_{\mathrm{so}}\mathrm{C}_{i}$ 通りある。

このとき、勝利数 $W$ の優勝候補者は、合計で $2\mathrm{ts}+\mathrm{ss}+\mathrm{to}+i$ 人である。
よって、自分が負ける場合の寄与は、tt=0 のときだけ次のようになる。

$$
\sum_{i=0}^{\mathrm{so}}
\frac{1}{2\mathrm{ts}+\mathrm{ss}+\mathrm{to}+i}
\times
{}_{\mathrm{so}}\mathrm{C}_{i}
\times
\left(\frac{1}{2}\right)^{\mathrm{ts}+\mathrm{to}+\mathrm{so}}
$$

pts は、この $2$ つの寄与を足した値である。

pst

pst は、ts の s 側の選手の優勝確率である。

pst の選手は、最後の試合に勝った場合だけ勝利数 $W$ になれる。
そして、tt=0 であり、ts と to の試合ではすべて t 側が負ける必要がある。

この条件は、pts の選手が自分の試合に負けて勝利数 $W$ で優勝候補者になる場合と同じである。
そのため、pst は pts の後半部分と同じ式で計算できる。

$$
\sum_{i=0}^{\mathrm{so}}
\frac{1}{2\mathrm{ts}+\mathrm{ss}+\mathrm{to}+i}
\times
{}_{\mathrm{so}}\mathrm{C}_{i}
\times
\left(\frac{1}{2}\right)^{\mathrm{ts}+\mathrm{to}+\mathrm{so}}
$$

ただし、tt>0 の場合は、勝利数 $W+1$ の選手が必ず生まれるので pst=0 である。

pss

pss は、ss の選手の優勝確率である。

ss の選手は、最後の試合に勝った場合だけ勝利数 $W$ になれる。
そのため、自分が勝つ確率 $\frac{1}{2}$ が必要である。
そして、tt=0 であり、ts と to の試合ではすべて t 側が負ける必要がある。

so の試合のうち、s 側が勝つ試合数を $i$ 個とする。
このとき、勝利数 $W$ の優勝候補者は $2\mathrm{ts}+\mathrm{ss}+\mathrm{to}+i$ 人である。

よって、pss は次のように計算できる。

$$
\sum_{i=0}^{\mathrm{so}}
\frac{1}{2\mathrm{ts}+\mathrm{ss}+\mathrm{to}+i}
\times
{}_{\mathrm{so}}\mathrm{C}_{i}
\times
\left(\frac{1}{2}\right)^{\mathrm{ts}+\mathrm{to}+\mathrm{so}+1}
$$

指数の $+1$ は、自分が ss の試合に勝つ必要があるためである。
ただし、tt>0 の場合は、勝利数 $W+1$ の選手が必ず生まれるので pss=0 である。

pto

pto は、to の t 側の選手の優勝確率である。

まず、自分が最後の試合に勝つ場合を考える。
この場合は、自分が ts+to 個の試合のうち t 側が勝った $i$ 人に含まれる必要がある。
よって、寄与は次のようになる。

$$
\sum_{i=1}^{\mathrm{ts}+\mathrm{to}}
\frac{1}{\mathrm{tt}+i}
\times
{}_{\mathrm{ts}+\mathrm{to}-1}\mathrm{C}_{i-1}
\times
\left(\frac{1}{2}\right)^{\mathrm{ts}+\mathrm{to}}
$$

次に、自分が最後の試合に負ける場合を考える。
この場合、tt=0 であり、ts と to の試合ではすべて t 側が負ける必要がある。

so の試合のうち、s 側が勝つ試合数を $i$ 個とすると、寄与は次のようになる。

$$
\sum_{i=0}^{\mathrm{so}}
\frac{1}{2\mathrm{ts}+\mathrm{ss}+\mathrm{to}+i}
\times
{}_{\mathrm{so}}\mathrm{C}_{i}
\times
\left(\frac{1}{2}\right)^{\mathrm{ts}+\mathrm{to}+\mathrm{so}}
$$

pto は、この $2$ つの寄与を足した値である。
つまり、式としては pts と同じ値になる。

pso

pso は、so の s 側の選手の優勝確率である。

pso の選手は、最後の試合に勝った場合だけ勝利数 $W$ になれる。
そして、tt=0 であり、ts と to の試合ではすべて t 側が負ける必要がある。

so の試合のうち、s 側が勝つ試合数を $i$ 個とする。
ただし、自分はその $i$ 人に含まれる必要がある。
そのため、試合の組は、残りの so-1 個の試合から $i-1$ 個を選ぶことになる。

このとき、勝利数 $W$ の優勝候補者は $2\mathrm{ts}+\mathrm{ss}+\mathrm{to}+i$ 人である。
よって、pso は次のように計算できる。

$$
\sum_{i=1}^{\mathrm{so}}
\frac{1}{2\mathrm{ts}+\mathrm{ss}+\mathrm{to}+i}
\times
{}_{\mathrm{so}-1}\mathrm{C}_{i-1}
\times
\left(\frac{1}{2}\right)^{\mathrm{ts}+\mathrm{to}+\mathrm{so}}
$$

ただし、tt>0 の場合は、勝利数 $W+1$ の選手が必ず生まれるので pso=0 である。

この計算では、二項係数と割り算を何度も使う。
そのため、階乗と階乗の逆元を前計算して、二項係数を高速に求められるようにしておく。

最後に、事前に記録しておいた選手ごとの仮の値に応じて、$6$ 種の値を代入すればよい。

階乗や累乗を適切な方法で行えば、計算量は $O(N \log \mathrm{MOD})$ 程度である。

入力例1での動作

入力を受け取る。

n: 4
a: {1, 2, 3, 4, 2, 3, 1, 4}

最大勝利数は $W=4$ なので、各選手を t、s、o に分類する。

最後の $4$ 試合を分類すると、次のようになる。

したがって、tt=0、ts=1、ss=0、to=1、so=1 である。

この入力例では tt と ss の試合は存在しない。
優勝確率を求める必要がある立場は pts、pst、pto、pso の $4$ 種類である。

pts は、ts の t 側である選手 $4$ の優勝確率である。
自分が勝って勝利数 $5$ になる場合を考える。
この場合の寄与は次のようになる。

$$
\frac{1}{1}\times{}_{1}\mathrm{C}_{0}\times\left(\frac{1}{2}\right)^2
+
\frac{1}{2}\times{}_{1}\mathrm{C}_{1}\times\left(\frac{1}{2}\right)^2
=
\frac{3}{8}
$$

自分が負けて勝利数 $4$ のまま優勝候補になる場合を考える。
この場合の寄与は次のようになる。

$$
\frac{1}{3}\times{}_{1}\mathrm{C}_{0}\times\left(\frac{1}{2}\right)^3
+
\frac{1}{4}\times{}_{1}\mathrm{C}_{1}\times\left(\frac{1}{2}\right)^3
=
\frac{7}{96}
$$

したがって、選手 $4$ の優勝確率は $\frac{43}{96}$、剰余表現では 883862188 である。

pst は、ts の s 側である選手 $3$ の優勝確率である。
自分が勝ち、かつ勝利数 $5$ の選手が生まれない場合だけ候補になる。
この場合の寄与は次のようになる。

$$
\frac{1}{3}\times{}_{1}\mathrm{C}_{0}\times\left(\frac{1}{2}\right)^3
+
\frac{1}{4}\times{}_{1}\mathrm{C}_{1}\times\left(\frac{1}{2}\right)^3
=
\frac{7}{96}
$$

剰余表現では 259959467 である。

pto は、to の t 側である選手 $8$ の優勝確率である。
この入力例では pts と同じ式になるので、$\frac{43}{96}$、剰余表現では 883862188 である。

pso は、so の s 側である選手 $6$ の優勝確率である。
自分が勝ち、かつ勝利数 $5$ の選手が生まれない場合だけ候補になる。
この場合の寄与は次のようになる。

$$
\frac{1}{4}\times{}_{0}\mathrm{C}_{0}\times\left(\frac{1}{2}\right)^3
=
\frac{3}{96}
$$

剰余表現では 967049217 である。

o の選手の優勝確率は $0$ である。
選手 $1$ から $8$ までの優勝確率は順に次のようになる。

0 0 259959467 883862188 0 967049217 0 883862188

注意点

答えは $998244353$ で割った余りを要求されているので、剰余類環の考えに従って処理する。
何か足し算や掛け算をするたびに結果を % 998244353 し、割り算は $998244353-2$ 乗したものを掛ける。
累乗計算を何度も行うため、繰り返し二乗法のアルゴリズムも用意しておくこと。

二項係数を階乗で計算するため、階乗と階乗の逆元を前計算しておくこと。

剰余の掛け算では $998244353^2$ 級の値が現れる。
long long 型または modint を用いること。

別解

特になし。