問題一覧 > 通常問題

No.3753 Certainly a Cretan

レベル : / AI推定難易度 : 2325 / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 21
作問者 : marc2825 / テスター : siganai
お気に入りにしたユーザー ProblemId : 13746 / 自分の提出
問題文最終更新日: 2026-08-29 00:54:56
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
yukicoder contest 516 (順位表) の他の問題:

Problem Statement

Numbered from $1$ to $N$, $N$ people stand in a line in order of their numbers. Each person is classified as one of two types: "honest person" or "liar".
When asked a yes-or-no question, an honest person always answers correctly, and a liar always gives the opposite of the correct answer.

Person $i$ answers the following question with Yes or No.

Among persons $1,2,\ldots,i$, do people of the same type as yourself make up a majority†?

You are given a string $S$ of length $N$ representing everyone's answers. $S_i=$ Y means that the answer of person $i$ is Yes, and $S_i=$ N means that it is No.
Process $Q$ queries on the string $S$ in order‡. There are $2$ types of queries, as follows.

  • 1 i: Flip the answer of person $i$, $S_i$. That is, if $S_i=$ Y, change it to N, and if $S_i=$ N, change it to Y.
  • 2 K: For the current $S$, output the number of assignments of types to the people such that there are exactly $K$ liars and everyone's answers match $S$, modulo $998244353$.

† A "majority" means, when the total number of people is $x$, at least $\left\lfloor \frac{x}{2} \right\rfloor + 1$ people.
‡ The queries are not independent. Changes to $S$ made by queries of type $1$ carry over to subsequent queries.

Constraints

  • $1 \leq N \leq 10^6$
  • $1 \leq Q \leq 10^5$
  • $S$ is a string of length $N$ consisting of Y and N
  • In queries of type $1$, $1 \leq i \leq N$
  • In queries of type $2$, $0 \leq K \leq N$
  • Queries of type $2$ appear at least $1$ time
  • $N,Q,i,K$ are integers

Input

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

$N$ $Q$
$S$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

Each query is given in one of the following formats. 

1 $i$
2 $K$

Output

Each time a query of type $2$ is given, output the answer to that query modulo $998244353$ on one line.

Sample

Sample 1
Input
4 6
NNNN
2 2
1 1
2 2
1 2
2 2
2 3
Output
2
0
1
1

Below, an honest person is denoted by H and a liar by L.
Initially, $S=$ NNNN. The assignments with exactly $2$ liars that satisfy the condition are LLHH and LHLH, for a total of $2$.
Next, flipping the answer of person $1$ gives $S=$ YNNN. Here, no assignment with exactly $2$ liars satisfies the condition.
Then, flipping the answer of person $2$ gives $S=$ YYNN. Here, the assignments that satisfy the condition are HLLH and HLLL, for a total of $2$. Their numbers of liars are $2$ and $3$ respectively, so the answers to the last $2$ queries are both $1$.

Sample 2
Input
53 17
YYYYYYYYYYYYYYNNNNNNNNNNNNNNYYYYYYYYYYYYYYYYNNNNNNNNN
2 27
2 30
1 53
2 26
1 53
2 28
1 11
2 0
1 12
2 27
2 28
1 11
2 53
1 12
2 29
2 30
2 31
Output
72814577
108940334
689767761
653642004
0
83916727
238511167
0
118112539
108940334
263178630

In query 1, the same $i$ may be chosen multiple times. Also, since the answer can be very large, output it modulo $998244353$.

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