ABC463F - 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}

最後の $N$ 試合の前での最大勝利数 mx を求める。

mx: 4

選手を t、s、o に分類する。

選手 1: o
選手 2: o
選手 3: s
選手 4: t
選手 5: o
選手 6: s
選手 7: o
選手 8: t

各試合を分類する。

第1試合: 選手1 vs 選手2 -> o 同士
第2試合: 選手3 vs 選手4 -> s と t
第3試合: 選手5 vs 選手6 -> o と s
第4試合: 選手7 vs 選手8 -> o と t

したがって、各種類の試合数は次のようになる。

tt: 0
ts: 1
ss: 0
to: 1
so: 1

各選手がどの種類の優勝確率を使うかを、result に仮の値として記録する。

result: {0, 0, -3, -2, 0, -6, 0, -5}

ここで、仮の値は次を表す。

-1: ptt
-2: pts
-3: pst
-4: pss
-5: pto
-6: pso

まず、ptt を計算する。
この入力例では tt=0 なので、ptt を使う選手はいない。

ptt は 0（実際の値は $0$）である。

次に、pts を計算する。
これは、ts の t 側の選手、つまり選手 $4$ の優勝確率である。

選手 $4$ が自分の試合に勝ち、勝利数 $W+1$ で優勝候補者になる場合の寄与は、次のようになる。

$$
\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$ が自分の試合に負け、勝利数 $W$ で優勝候補者になる場合の寄与は、次のようになる。

$$
\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}
$$

よって、pts は次の値になる。

pts は 883862188（実際の値は $\frac{43}{96}$）である。

次に、pst を計算する。
これは、ts の s 側の選手、つまり選手 $3$ の優勝確率である。

pst の選手は、自分の試合に勝った場合だけ勝利数 $W$ で優勝候補者になりうる。
この入力例では、寄与は次の値になる。

$$
\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}
$$

したがって、pst は次の値になる。

pst は 259959467（実際の値は $\frac{7}{96}$）である。

次に、pss を計算する。
この入力例では ss=0 なので、pss を使う選手はいない。

pss は 0（実際の値は $0$）である。

次に、pto を計算する。
これは、to の t 側の選手、つまり選手 $8$ の優勝確率である。

この入力例では、pto は pts と同じ値になる。

pto は 883862188（実際の値は $\frac{43}{96}$）である。

次に、pso を計算する。
これは、so の s 側の選手、つまり選手 $6$ の優勝確率である。

選手 $6$ が優勝候補者になるには、自分の試合に勝つ必要がある。
この入力例では、寄与は次の値になる。

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

したがって、pso は次の値になる。

pso は 967049217（実際の値は $\frac{3}{96}$）である。

最後に、result の仮の値を実際の優勝確率に置き換える。

result: {0, 0, 259959467, 883862188, 0, 967049217, 0, 883862188}

実際の値は、順に $0,0,\frac{7}{96},\frac{43}{96},0,\frac{3}{96},0,\frac{43}{96}$ である。

よって、0 0 259959467 883862188 0 967049217 0 883862188 を出力する。

注意点

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

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

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

別解

特になし。