結果
問題 | No.196 典型DP (1) |
ユーザー |
![]() |
提出日時 | 2024-09-02 11:44:39 |
言語 | Scala(Beta) (3.6.2) |
結果 |
RE
|
実行時間 | - |
コード長 | 1,114 bytes |
コンパイル時間 | 9,800 ms |
コンパイル使用メモリ | 262,316 KB |
実行使用メモリ | 92,840 KB |
最終ジャッジ日時 | 2024-09-02 11:45:42 |
合計ジャッジ時間 | 62,401 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 35 RE * 6 |
ソースコード
import scala.io.StdIn.readLineimport scala.collection.mutable.ArrayBuffer@maindef yuki196(): Unit =val MOD = 1000000007Lval Array(n, k) = readLine.split(" ").map(_.toInt)val graph = Array.fill(n)(ArrayBuffer[Long]())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[Long]())def dfs(cur: Long): Unit =visited(cur.toInt) = truesize(cur.toInt) = 1var dpCur: ArrayBuffer[Long] = ArrayBuffer(1)fornext <- graph(cur.toInt)if !visited(next.toInt)dodfs(next)val dpNext = dp(next.toInt)val ndp = ArrayBuffer.fill(size(cur.toInt) + size(next.toInt) - 1)(0L)fori <- dpCur.indicesj <- dpNext.indicesdondp(i + j) = (ndp(i + j) + dpCur(i) * dpNext(j)) % MODdpCur = ndpsize(cur.toInt) += size(next.toInt) - 1dpCur.append(1)size(cur.toInt) += 1dp(cur.toInt) = dpCurdfs(0)println(dp(0)(k))