問題一覧 > 通常問題

No.2742 Car Flow

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 49
作問者 : tassei903tassei903 / テスター : kenken714kenken714 Nzt3Nzt3 ponjuiceponjuice
3 ProblemId : 10828 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-04-19 01:07:19

問題文

$0$ と $1$ のみからなる長さ $N$ の数列 $A = (A_0, A_1, \dots, A_{N-1})$ が与えられる。

それぞれが長さ $N$ の数列 $B_0, B_1, B_2\dots$ が次のように定義されます。

  • $B_{0,j} = A_j (0 \le j \lt N)$

  • $B_{i+1,j}=\begin{cases}1 (B_{i,(j-1) \text{ mod } N}=1\text{かつ} B_{i,j}=0)\text{または}(B_{i,j}=1\text{かつ}B_{i,(j+1)\text{ mod }N}=1))\\0 (\text{それ以外})\end{cases}$

以下の極限が有理数に収束することが証明できるのでそれを求めて、$\text{mod } 998244353$ で出力してください。

$\lim_{T\rightarrow\infty}\frac{1}{T}\sum_{i=0}^{T-1} B_{i+1,0}\times (1 - B_{i,0})$

有理数 $\text{ mod } 998244353$ とは 有理数を出力する際は、まずその有理数を分数 $\frac{y}{x}$ として表してください。ここで、 $x$, $y$ は整数であり、 $x$ は $998244353$ で割り切れてはなりません (この問題の制約下で、そのような表現は必ず可能です)。 そして、$xz ≡ y (\text{mod } 998244353 )$ を満たすような $0$ 以上 $998244353$ 以下の唯一の整数 $z$ を出力してください。

制約

  • 入力はすべて整数
  • $3 \le N\le 2\times 10^5$
  • $A_i=0,1$ $ (i=0,1,\dots, N-1)$

入力

入力は以下の形式で標準入力から与えられます．

$N$
$A_0$ $A_1$ $\dots$ $A_{N-1}$

出力

答えを $\text{mod } 998244353$ で出力してください。

サンプル

サンプル1
入力
3
0 1 0
出力
332748118

$B_0 = (0, 1, 0)$

$B_1 = (0, 0, 1)$

$B_2 = (1, 0, 0)$

$B_3 = (0, 1, 0)$

$\vdots$

と続いていきます。求める極限は $\frac{1}{3}$ です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。