問題一覧 > 通常問題

No.2742 Car Flow

レベル : / AI推定難易度 : 1625 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 53
作問者 : tassei903 / テスター : kenken714 Nzt3 ponjuice
お気に入りにしたユーザー ProblemId : 10828 / 自分の提出
問題文最終更新日: 2026-10-20 09:08:51
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
CPCTF 2024 : PPC (順位表) の他の問題:

Problem Statement

You are given a sequence $A = (A_0, A_1, \dots, A_{N-1})$ of length $N$ consisting only of $0$ and $1$.

Sequences $B_0, B_1, B_2\dots$, each of length $N$, are defined as follows.

  • $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{ and } B_{i,j}=0)\text{ or }(B_{i,j}=1\text{ and }B_{i,(j+1)\text{ mod }N}=1))\\0 (\text{otherwise})\end{cases}$

It can be proved that the following limit converges to a rational number. Find it and print it $\text{mod } 998244353$.

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

What is a rational number $\text{ mod } 998244353$? To output a rational number, first represent it as a fraction $\frac{y}{x}$. Here, $x$ and $y$ are integers, and $x$ must not be divisible by $998244353$ (under the constraints of this problem, such a representation is always possible). Then, print the unique integer $z$ satisfying $xz ≡ y (\text{mod } 998244353 )$ that is at least $0$ and less than $998244353$.

Constraints

  • All input values are integers.
  • $3 \le N\le 2\times 10^5$
  • $A_i=0,1$ $ (i=0,1,\dots, N-1)$

Input

The input is given from standard input in the following format.

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

Output

Print the answer $\text{mod } 998244353$.

Sample

Sample 1
Input
3
0 1 0
Output
332748118

$B_0 = (0, 1, 0)$

$B_1 = (0, 0, 1)$

$B_2 = (1, 0, 0)$

$B_3 = (0, 1, 0)$

$\vdots$

The sequences continue in this way. The limit to be found is $\frac{1}{3}$.

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