結果
問題 | No.196 典型DP (1) |
ユーザー | 👑 hos.lyric |
提出日時 | 2019-01-10 17:11:28 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 34 ms / 2,000 ms |
コード長 | 2,114 bytes |
コンパイル時間 | 780 ms |
コンパイル使用メモリ | 119,692 KB |
実行使用メモリ | 23,760 KB |
最終ジャッジ日時 | 2024-06-13 02:34:24 |
合計ジャッジ時間 | 2,824 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
import std.conv, std.stdio, std.string; import std.algorithm, std.array, std.bigint, std.container, std.math, std.range, std.regex, std.typecons; import core.bitop; class EOFException : Throwable { this() { super("EOF"); } } string[] tokens; string readToken() { for (; tokens.empty; ) { if (stdin.eof) throw new EOFException; tokens = readln.split; } auto token = tokens[0]; tokens.popFront; return token; } int readInt() { return readToken().to!int; } long readLong() { return readToken().to!long; } real readReal() { return readToken().to!real; } void chmin(T)(ref T t, in T f) { if (t > f) t = f; } void chmax(T)(ref T t, in T f) { if (t < f) t = f; } int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = cast(int)(as.length); for (; low + 1 < upp; ) { int mid = (low + upp) >> 1; (test(as[mid]) ? low : upp) = mid; } return upp; } int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a < val)); } int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a <= val)); } immutable MO = 1_000_000_007L; int N, K; int[] A, B; int[][] G; int[] sz; long[][] dp; void dfs(int u, int p) { foreach (v; G[u]) { if (v != p) { dfs(v, u); } } sz[u] = 0; dp[u] = [1]; foreach (v; G[u]) { if (v != p) { auto nxt = new long[sz[u] + sz[v] + 1]; foreach (x; 0 .. sz[u] + 1) foreach (y; 0 .. sz[v] + 1) { (nxt[x + y] += dp[u][x] * dp[v][y]) %= MO; } sz[u] += sz[v]; dp[u] = nxt; } } sz[u] += 1; dp[u] ~= 1; debug { writefln("sz[%s] = %s", u, sz[u]); writefln("dp[%s] = %s", u, dp[u]); } } void main() { try { for (; ; ) { N = readInt(); K = readInt(); A = new int[N - 1]; B = new int[N - 1]; foreach (i; 0 .. N - 1) { A[i] = readInt(); B[i] = readInt(); } G = new int[][N]; foreach (i; 0 .. N - 1) { G[A[i]] ~= B[i]; G[B[i]] ~= A[i]; } sz = new int[N]; dp = new long[][N]; dfs(0, -1); writeln(dp[0][K]); } } catch (EOFException e) { } }