Kotlin Heroes: Episode 6 |
---|
Finished |
You are given an integer $$$n$$$ and a sequence $$$a$$$ of $$$n-1$$$ integers, each element is either $$$0$$$ or $$$1$$$.
You are asked to build a string of length $$$n$$$ such that:
You will be asked $$$q$$$ queries of form:
After each query print the number of different strings that satisfy the given constraints modulo $$$998\,244\,353$$$.
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 10^5$$$; $$$1 \le q \le 10^5$$$) — the length of the string and the number of queries.
The second line contains $$$n-1$$$ integers $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$a_i \in \{0, 1\}$$$) — the constraints on suffixes of the string.
Each of the next $$$q$$$ lines contains a query: an integer $$$i$$$ ($$$1 \le i \le n - 1$$$) — flip the value of $$$a_i$$$ (if $$$a_i=0$$$, then set $$$a_i$$$ to $$$1$$$, and vice versa).
After each query print the number of different strings that satisfy the given constraints modulo $$$998\,244\,353$$$.
2 2 0 1 1
6 10
3 4 0 0 1 2 1 2
20 10 14 20
10 10 0 0 0 1 1 1 0 1 0 4 1 8 4 2 9 5 6 6 8
1815 3201 2710 2776 2290 1644 2668 1271 2668 2436
The $$$i$$$-th suffix of a string is a continuous substring that starts from the $$$i$$$-th position and ends in the last position.
A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:
Two strings $$$a$$$ and $$$b$$$ of length $$$n$$$ differ if there exists a position $$$i$$$ such that $$$a_i \neq b_i$$$.
Name |
---|