問題一覧 > 通常問題

No.3098 Linear Reversi

レベル : / AI推定難易度 : 2600 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 15
作問者 : RiRinbaru / テスター : autumn09 downer hamo21 ygussany Yotugi
お気に入りにしたユーザー ProblemId : 11592 / 自分の提出
問題文最終更新日: 2025-04-06 13:28:00
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
QUPC2024 (順位表) の他の問題:

Problem Statement

There is an Othello board that is $N$ squares wide and $1$ square tall. Let $A_i$ denote the $i$-th square from the left of the board. Initially, no pieces are placed on the board.
You perform the following operation $N$ times: choose $1$ square that does not yet have a piece on it, freely decide whether black or white faces up, and place $1$ Othello piece there. Here, the color facing up on a piece is called the "color of the piece". The colors of the pieces get flipped in the same way as in the rules of Othello.

Specifically, for squares $A_x$ , $A_{x+1}$ , $...$ $A_{y-1}$ , $A_y$ ,

  • When all of them except $A_y$ have pieces on them and, among those, only the piece on $A_x$ has a different color, placing a piece on $A_y$ with the same color facing up as the piece on $A_x$ makes the colors of the pieces on $A_{x+1}$ , $A_{x+2}$ , $...$ $A_{y-1}$ equal to that of the piece on $A_y$.
  • When all of them except $A_x$ have pieces on them and, among those, only the piece on $A_y$ has a different color, placing a piece on $A_x$ with the same color facing up as the piece on $A_y$ makes the colors of the pieces on $A_{x+1}$ , $A_{x+2}$ , $...$ $A_{y-1}$ equal to that of the piece on $A_x$.
These are the rules that apply. Note that, unlike in ordinary Othello, you may consecutively place pieces with the same color facing up, and you may place a piece at a position where no piece colors get flipped.

You are given a string $S$. The $i$-th character of $S$ means the following:

  • If it is o, a piece is placed on $A_i$ with white facing up.
  • If it is x, a piece is placed on $A_i$ with black facing up.
  • If it is ?, the color of the piece on $A_i$ is missing and unknown.

Letting $M$ be the number of missing parts, there are $2^M$ ways to fill them with white or black pieces. Among these, find the number of final configurations achievable under the above rules, modulo $998244353$.

Input

The input is given from standard input in the following format.
$N$
$S$
  • $1≦N≦10^6$
  • $|S|=N$
  • All inputs are integers.

Output

Output the number of achievable Othello board configurations, modulo $998244353$. Print a newline at the end.

Sample

Sample 1
Input
3
ox?
Output
2

Sample 2
Input
5
ox??o
Output
3

Sample 3
Input
10
??????????
Output
488

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