問題一覧 > 通常問題

No.2360 Path to Integer

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 2.500秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 63
作問者 : 👑 qand / テスター : ygussany とりゐ
お気に入りにしたユーザー ProblemId : 8804 / 自分の提出
問題文最終更新日: 2023-06-09 20:17:29
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 394 (順位表) の他の問題:

Problem Statement

You are given a tree $G$ with $N$ vertices. The $i$-th $(1\le i\le N-1)$ edge of the tree $G$ connects vertex $u_i$ and vertex $v_i$. Also, a string $A_i$ is written on the $i$-th $(1\le i\le N)$ vertex.

Define $f(i,j)$ as the integer obtained by the following procedure.

  • Let $S$ be the empty string.
  • For all vertices on the shortest path from vertex $i$ to vertex $j$, in order starting from vertex $i$, append the string written on that vertex to the end of $S$.
  • The value of $S$ regarded as an integer is $f(i,j)$.

Find $\displaystyle \sum_{i=1}^N\sum_{j=1}^Nf(i,j)$ modulo $998244353$.

Constraints

  • $2\le N\le 10^5$
  • $A_i$ is a string of length between $1$ and $10$, inclusive, consisting of digits from 0 to 9, and its first character is not 0.
  • $1\le u_i,v_i\le N$
  • The given graph is a tree.

    • Input

    $N$
$A_1$ $A_2$ $\ldots$ $A_N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$

    Output

    Output $\displaystyle \sum_{i=1}^N\sum_{j=1}^Nf(i,j)$ modulo $998244353$.

    Sample

    Sample 1
    Input
    3
2 1 12
1 2
2 3
    Output
    3605

    For example, $f(1,3)=2112$. This is because $2,1,12$ are written on vertices $1,2,3$ respectively, and concatenating them gives $2112$.
    The answer is $2+21+2112+12+1+112+1212+121+12=3605$, so output $3605$.

    Sample 2
    Input
    4
998244353 998244353 998244353 1
1 2
1 3
1 4
    Output
    435653094

    Output the remainder when divided by $998244353$.

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