問題一覧 > 通常問題

No.3053 $((0 \And 1)\mathop{|}2)\oplus 3$

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 15
作問者 : suisen / テスター : kaichou243 👑 rin204
お気に入りにしたユーザー ProblemId : 11852 / 自分の提出
問題文最終更新日: 2025-01-20 01:01:40
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 459 (順位表) の他の問題:

Problem Statement

You are given a positive integer $N$.

For a sequence of binary operators $\mathrm{op} = (\mathrm{op} _ 1, \mathrm{op} _ 2, \ldots, \mathrm{op} _ N)$ of length $N$, where each element is one of $\And,|,\oplus$, define $f(\mathrm{op})$ as follows.

$$ f(\mathrm{op}) \coloneqq (\cdots ((0 \mathop{\mathrm{op} _ 1} 1 ) \mathop{\mathrm{op} _ 2} 2) \cdots )\mathop{\mathop{\mathrm{op} _ N}} N. $$

Here, $\And$ denotes bitwise AND, $|$ denotes bitwise OR, and $\oplus$ denotes bitwise XOR.

For example, for $N=3$ and $\mathrm{op}=(\And,|,\oplus)$, we have $f(\mathrm{op}) = ((0 \mathop{\And} 1) \mathop{|} 2) \oplus 3 = (0\mathop{|} 2) \oplus 3 = 2 \oplus 3 = 1$.

There are $3 ^ N$ sequences $\mathrm{op}$ of binary operators of length $N$ where each element is one of $\And,|,\oplus$. Find the sum of $f(\mathrm{op})$ over all such $\mathrm{op}$, modulo $998244353$.

Input

The input is given from Standard Input in the following format.

$N$
  • $1\leq N \lt 2 ^ {1,000,000}$
  • $N$ is given as an integer in binary notation. It is also guaranteed that it has no extra leading $0$s.

Output

Print the sum of $f(\mathrm{op})$ modulo $998244353$ in decimal notation on $1$ line, followed by a newline.

Sample

Sample 1
Input
10
Output
16

Since $N$ is given in binary notation, this input is $N = 10_{(2)} = 2_{(10)}$. That is, it represents $N=2$ in decimal notation.

In the following explanation, all numbers are in decimal notation.

For example, when $\mathrm{op} = (\And,|)$, we have $f(\mathrm{op}) = (0 \And 1) \mathop{|} 2 = 0 \mathop{|} 2= 2$. The sum of $f(\mathrm{op})$ over the $3 ^ 2$ sequences $\mathrm{op}$ is $16$.

Therefore, print $16$, the remainder when $16$ is divided by $998244353$, in decimal notation.

Sample 2
Input
10101100101011001010001001
Output
354528097

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