結果
問題 | No.196 典型DP (1) |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
import scala.io.StdIn.readLineimport scala.collection.mutable.ArrayBuffer@maindef yuki196(): Unit =val MOD = 1000000007val Array(n, k) = readLine.split(" ").map(_.toInt)val graph = Array.fill(n)(ArrayBuffer[Int]())for_ <- 1 until ndoval 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) = truesize(cur) = 1var dpCur = ArrayBuffer(1)fornext <- graph(cur)if !visited(next)dodfs(next)val dpNext = dp(next)val ndp = ArrayBuffer.fill(size(cur) + size(next) - 1)(0)fori <- dpCur.indicesj <- dpNext.indicesdondp(i + j) = (ndp(i + j) + dpCur(i) * dpNext(j)) % MODdpCur = ndpsize(cur) += size(next) - 1dpCur.append(1)size(cur) += 1dp(cur) = dpCurdfs(0)println(dp(0)(k))