No.2742 Car Flow
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もしくは右上の雲マークをクリックしてアカウントを作成してください。