問題一覧 > 通常問題

No.2129 Perfect Binary Tree...?

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 13
作問者 : 遭難者遭難者 / テスター : PCTprobabilityPCTprobability 👑 potato167potato167
0 ProblemId : 8733 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-11-18 20:49:05

問題文

2N12^N-1 頂点 2N12^N-1 辺の無向グラフ GG があります。

GG11 番目の辺は頂点 uu と頂点 vv を結んでおり、 xx 番目 (2x2N1)(2\le x\le 2^N-1) の辺は頂点 x/2\lfloor x/2 \rfloor と頂点 xx を結んでいます。

d(i,j)d(i,j)GG 上での頂点 ii と頂点 jj の距離とします。

1i<j2N1d(i,j)\displaystyle \sum_{1\le i< j\le 2^N-1} d(i,j)998244353998244353 で割った余りを求めてください。

ただし、 x/2\lfloor x/2 \rfloorx/2x/2 以下の最大の整数を表します。

制約

  • 2N2×1052\le N\le 2\times 10^5
  • 1u,v2N11\le u,v\le 2^N-1
  • u,vu,v は先頭が 00 でない二進数で与えられる。
  • 入力は全て整数である。
  • 入力

    NN
    uu
    vv
    

    出力

    1i<j2N1d(i,j)\displaystyle \sum_{1\le i< j\le 2^N-1} d(i,j)998244353998244353 で割った余りを出力してください。

    サンプル

    サンプル1
    入力
    2
    10
    11
    出力
    3

    頂点 22 と 頂点 33 、頂点 11 と 頂点 22 、頂点 11 と 頂点 33 に辺が張られています。
    よって、 1i<j31\le i < j\le 3 に対し d(i,j)=1d(i,j)=1 となります。したがって、 33 を出力してください。

    サンプル2
    入力
    3
    1
    1
    出力
    48

    u=vu=v となる場合もあります。

    サンプル3
    入力
    8
    1101
    101
    出力
    314684

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。