問題一覧 > 通常問題

No.2129 Perfect Binary Tree...?

レベル : / AI推定難易度 : 2325 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 14
作問者 : 👑 qand / テスター : PCTprobability 👑 potato167
お気に入りにしたユーザー ProblemId : 8733 / 自分の提出
問題文最終更新日: 2022-11-18 20:49:05
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 368 (順位表) の他の問題:

Problem Statement

There is an undirected graph $G$ with $2^N-1$ vertices and $2^N-1$ edges.

The $1$-st edge of $G$ connects vertex $u$ and vertex $v$, and the $x$-th edge $(2\le x\le 2^N-1)$ connects vertex $\lfloor x/2 \rfloor$ and vertex $x$.

Let $d(i,j)$ be the distance between vertex $i$ and vertex $j$ on $G$.

Find $\displaystyle \sum_{1\le i< j\le 2^N-1} d(i,j)$ modulo $998244353$.

Here, $\lfloor x/2 \rfloor$ denotes the largest integer less than or equal to $x/2$.

Constraints

  • $2\le N\le 2\times 10^5$
  • $1\le u,v\le 2^N-1$
  • $u,v$ are given in binary, with no leading $0$.
  • All inputs are integers.

    • Input

    $N$
$u$
$v$

    Output

    Print $\displaystyle \sum_{1\le i< j\le 2^N-1} d(i,j)$ modulo $998244353$.

    Sample

    Sample 1
    Input
    2
10
11
    Output
    3

    There are edges between vertex $2$ and vertex $3$, vertex $1$ and vertex $2$, and vertex $1$ and vertex $3$.
    Thus, $d(i,j)=1$ for $1\le i < j\le 3$. Therefore, print $3$.

    Sample 2
    Input
    3
1
1
    Output
    48

    It is possible that $u=v$.

    Sample 3
    Input
    8
1101
101
    Output
    314684

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