No.2129 Perfect Binary Tree...?
タグ : / 解いたユーザー数 13
作問者 :
遭難者
/ テスター :
PCTprobability
👑 
potato167
問題文
$2^N-1$ 頂点 $2^N-1$ 辺の無向グラフ $G$ があります。
$G$ の $1$ 番目の辺は頂点 $u$ と頂点 $v$ を結んでおり、 $x$ 番目 $(2\le x\le 2^N-1)$ の辺は頂点 $\lfloor x/2 \rfloor$ と頂点 $x$ を結んでいます。
$d(i,j)$ を $G$ 上での頂点 $i$ と頂点 $j$ の距離とします。
$\displaystyle \sum_{1\le i< j\le 2^N-1} d(i,j)$ を $998244353$ で割った余りを求めてください。
ただし、 $\lfloor x/2 \rfloor$ は $x/2$ 以下の最大の整数を表します。
制約
入力
$N$ $u$ $v$
出力
$\displaystyle \sum_{1\le i< j\le 2^N-1} d(i,j)$ を $998244353$ で割った余りを出力してください。
サンプル
サンプル1
入力
2 10 11
出力
3
頂点 $2$ と 頂点 $3$ 、頂点 $1$ と 頂点 $2$ 、頂点 $1$ と 頂点 $3$ に辺が張られています。
よって、 $1\le i < j\le 3$ に対し $d(i,j)=1$ となります。したがって、 $3$ を出力してください。
サンプル2
入力
3 1 1
出力
48
$u=v$ となる場合もあります。
サンプル3
入力
8 1101 101
出力
314684
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。