No.3053 $((0 \And 1)\mathop{|}2)\oplus 3$
タグ : / 解いたユーザー数 10
作問者 :
suisen
/ テスター :
kaichou243
👑 
rin204
問題文
正整数 $N$ が与えられます。
各要素が $\And,|,\oplus$ のいずれかである長さ $N$ の二項演算子の列 $\mathrm{op} = (\mathrm{op} _ 1, \mathrm{op} _ 2, \ldots, \mathrm{op} _ N)$ に対して、$f(\mathrm{op})$ を以下のように定義します。
$$ f(\mathrm{op}) \coloneqq (\cdots ((0 \mathop{\mathrm{op} _ 1} 1 ) \mathop{\mathrm{op} _ 2} 2) \cdots )\mathop{\mathop{\mathrm{op} _ N}} N. $$
ここで、$\And$ はビットごとの論理積、$|$ はビットごとの論理和、$\oplus$ はビットごとの排他的論理和を表します。
例えば $N=3$ と $\mathrm{op}=(\And,|,\oplus)$ に対しては $f(\mathrm{op}) = ((0 \mathop{\And} 1) \mathop{|} 2) \oplus 3 = (0\mathop{|} 2) \oplus 3 = 2 \oplus 3 = 1$ となります。
各要素が $\And,|,\oplus$ のいずれかである長さ $N$ の二項演算子の列 $\mathrm{op}$ は $3 ^ N$ 通りありますが、その全ての $\mathrm{op}$ に対する $f(\mathrm{op})$ の総和を $998244353$ で割った余りを求めてください。
入力
入力は以下の形式で標準入力から与えられる。
$N$
- $1\leq N \lt 2 ^ {1,000,000}$
- $N$ は二進表記の整数として与えられる。また先頭に余分な $0$ を含まないことが保証される。
出力
$f(\mathrm{op})$ の総和を $998244353$ で割った余りを 十進表記 で $1$ 行に出力して改行してください。
サンプル
サンプル1
入力
10
出力
16
$N$ は二進表記で与えられるので、この入力は $N = 10_{(2)} = 2_{(10)}$ です。つまり、十進表記で $N=2$ を表します。
以下、数値は十進表記であるとして説明します。
例えば $\mathrm{op} = (\And,|)$ のとき $f(\mathrm{op}) = (0 \And 1) \mathop{|} 2 = 0 \mathop{|} 2= 2$ です。$3 ^ 2$ 通りの $\mathrm{op}$ に対する $f(\mathrm{op})$ の総和は $16$ となります。
従って、$16$ を $998244353$ で割った余りである $16$ を十進表記で出力します。
サンプル2
入力
10101100101011001010001001
出力
354528097
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。