No.3053 $((0 \And 1)\mathop{|}2)\oplus 3$
タグ : / 解いたユーザー数 15
作問者 :
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もしくは右上の雲マークをクリックしてアカウントを作成してください。