結果

問題 No.196 典型DP (1)
ユーザー scaler
提出日時 2024-09-02 11:39:14
言語 Scala(Beta)
(3.6.2)
結果
WA  
実行時間 -
コード長 1,024 bytes
コンパイル時間 10,890 ms
コンパイル使用メモリ 265,460 KB
実行使用メモリ 104,568 KB
最終ジャッジ日時 2024-09-02 11:40:21
合計ジャッジ時間 64,016 ms
ジャッジサーバーID
(参考情報)
judge3 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 21 WA * 15 RE * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import scala.io.StdIn.readLine
import scala.collection.mutable.ArrayBuffer
@main
def yuki196(): Unit =
val MOD = 1000000007
val Array(n, k) = readLine.split(" ").map(_.toInt)
val graph = Array.fill(n)(ArrayBuffer[Int]())
for
_ <- 1 until n
do
val Array(u, v) = readLine.split(" ").map(_.toInt)
graph(u).append(v)
graph(v).append(u)
val visited = Array.fill(n)(false)
val size = Array.fill(n)(0)
val dp = Array.fill(n)(ArrayBuffer[Int]())
def dfs(cur: Int): Unit =
visited(cur) = true
size(cur) = 1
var dpCur = ArrayBuffer(1)
for
next <- graph(cur)
if !visited(next)
do
dfs(next)
val dpNext = dp(next)
val ndp = ArrayBuffer.fill(size(cur) + size(next) - 1)(0)
for
i <- dpCur.indices
j <- dpNext.indices
do
ndp(i + j) = (ndp(i + j) + dpCur(i) * dpNext(j)) % MOD
dpCur = ndp
size(cur) += size(next) - 1
dpCur.append(1)
size(cur) += 1
dp(cur) = dpCur
dfs(0)
println(dp(0)(k))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0