No.2083 OR Subset
タグ : / 解いたユーザー数 24
作問者 :
taiga0629kyopro
/ テスター :
hamamu
ygussany
問題文
$\lbrace 1,2,3, \dots , 2^N-1 \rbrace$ の部分集合 $X=\left \lbrace X_1, X_2, \dots, X_k \right \rbrace$ に対して、 $f(X)=X_1\ \mathrm{OR}\ X_2\ \mathrm{OR} \dots \mathrm{OR}\ X_k$ と定義します。ただし、$X$ が空集合の時は $f(X)=0$ とします。
$\lbrace 1,2,3, \dots , 2^N-1 \rbrace$ の部分集合 $S$ のうち次の条件を満たすものを良い集合と呼ぶことにします。
- $S$ の任意の部分集合 $U$, $V$ に対して、$U \neq V$ ならば $f(U) \neq f(V)$ が成り立つ。
$\lbrace 1,2,3, \dots , 2^N-1 \rbrace$ の部分集合 $S$ は $2^{2^N-1}$ 個ありますが、そのうち良い集合の個数を求め、 $998244353$ で割った余りを出力してください。
$\mathrm{OR}$ とは（クリックで開く）
$\mathrm{OR}$ はビットごとの論理和を表します。
入力
$N$
出力
良い集合の個数を $998244353$ で割った余りを出力してください。
サンプル
サンプル1
入力
2
出力
5
条件を満たす $S$ は $ \lbrace \rbrace$, $ \lbrace 1 \rbrace$, $ \lbrace 2 \rbrace$, $ \lbrace 3 \rbrace$, $ \lbrace 1,2 \rbrace$ の 5つです。
サンプル2
入力
4
出力
98
サンプル3
入力
100
出力
457732232
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。