No.2904 Distinct Multisets in a Way
タグ : / 解いたユーザー数 22
作問者 : 👑
amentorimaru
cleantted
👑 
Nachia
問題文
この問題では、要素数が $K$ で要素が $e_1,e_2,e_3,\ldots,e_{K}$ である多重集合を $\{\!|e_1,e_2,e_3,\ldots,e_{K}|\!\}$ と表します。
多重集合 $S$ から、任意の要素が $1/|S|$ の確率で取られるように要素を $1$ つ取る操作を考えます。
$2$ つの空でない多重集合の組 $(S_1,S_2)$ について、この操作を $1$ 回ずつ $S_1$ と $S_2$ に独立して行って取った要素の和の確率分布を $P(S_1,S_2)$ とします。
以下の条件を全て満たす $2$ つの多重集合の組 $(S_1,S_2)$ の個数を $998244353$ で割った余りを求めてください。ただし、 $(S_1,S_2)=(S_2,S_1)$ として同一視します。
- $|S_1|=|S_2|=2^N$
- $S_1$ および $S_2$ の全ての要素は正の整数である。
- $(S_1,S_2)\neq (\{\!|1,2,3,\ldots,2^N|\!\},\ \{\!|1,2,3,\ldots,2^N|\!\})$
- $P(S_1,S_2)=P(\{\!|1,2,3,\ldots,2^N|\!\},\ \{\!|1,2,3,\ldots,2^N|\!\})$
入力
$N$
- 入力は全て整数
- $0\leq N\leq 5\times 10^5$
出力
組の個数を $998244353$ で割った余りを出力し、最後に改行してください。
サンプル
サンプル1
入力
3
出力
3
$2^3=8$ です。
$(\{\!|1,2,2,3,3,4,4,5|\!\},\ \{\!|1,3,5,5,7,7,9,11|\!\}),\ (\{\!|1,2,3,3,4,4,5,6|\!\},\ \{\!|1,2,5,5,6,6,9,10|\!\}),\ (\{\!|1,2,2,3,5,6,6,7|\!\},\ \{\!|1,3,3,5,5,7,7,9|\!\})$ の $3$ 組が条件を満たします。
全ての組について $P$ は、確率 $1/64$ で $2$ 、確率 $1/32$ で $3$ 、確率 $3/64$ で $4$ 、確率 $1/16$ で $5$ 、確率 $5/64$ で $6$ 、確率 $3/32$ で $7$ 、確率 $7/64$ で $8$ 、確率 $1/8$ で $9$ 、確率 $7/64$ で $10$ 、確率 $3/32$ で $11$ 、確率 $5/64$ で $12$ 、確率 $1/16$ で $13$ 、確率 $3/64$ で $14$ 、確率 $1/32$ で $15$ 、確率 $1/64$ で $16$ をとる確率分布となります。
この分布は、 $P(\{\!|1,2,3,4,5,6,7,8|\!\},\ \{\!|1,2,3,4,5,6,7,8|\!\})$ と一致します。
例として、組 $(\{\!|1,2,2,3,3,4,4,5|\!\},\ \{\!|1,3,5,5,7,7,9,11|\!\})$ について要素の和が $4$ となる確率について確認します。
確認のためにそれぞれの数を $(\{1,2_1,2_2,3_1,3_2,4_1,4_2,5\},\ \{1',3',5'_1,5'_2,7'_1,7'_2,9',11'\})$ と置き換えると、要素の和が $4$ となる取り方は $(1,3'),\ (3_1,1'),\ (3_2,1')$ の $3$ 通りであり、確かに確率 $3/64$ で $4$ となります。
サンプル2
入力
500000
出力
329966357
$998244353$ で割った余りを求めてください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。