結果
問題 | No.196 典型DP (1) |
ユーザー | airis |
提出日時 | 2015-05-10 15:16:53 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 39 ms / 2,000 ms |
コード長 | 1,492 bytes |
コンパイル時間 | 728 ms |
コンパイル使用メモリ | 80,724 KB |
実行使用メモリ | 35,328 KB |
最終ジャッジ日時 | 2024-07-05 21:25:31 |
合計ジャッジ時間 | 2,991 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <iostream> #include <algorithm> #include <string> #include <vector> #include <queue> #include <stack> #include <set> #include <map> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <numeric> #define rep(x, to) for (int x = 0; x < (to); x++) #define REP(x, a, to) for (int x = (a); x < (to); x++) #define foreach(itr, x) for (typeof((x).begin()) itr = (x).begin(); itr != (x).end(); itr++) using namespace std; typedef long long ll; typedef pair<int, int> PII; typedef pair<long, long> PLL; const ll MOD = (ll)(1e+9 + 7); int N, K; vector<int> G[2005]; vector<ll> dp[2005]; //dp[i][j] iを根とした部分グラフにj個塗る場合は何通りあるか ll dfs(int cur, int prev) { int sum = 1; //curを根とした部分グラフに存在する頂点の数 dp[cur][0] = 1; rep(i, G[cur].size()) { int adj = G[cur][i]; // 隣接ノード if (adj == prev) continue; int num = dfs(adj, cur); vector<ll> tmp(2005, 0); for (int j = 0; j <= sum; j++) { for (int k = 0; k <= num; k++) { tmp[j + k] += (dp[cur][j] * dp[adj][k]) % MOD; tmp[j + k] %= MOD; } } dp[cur] = tmp; sum += num; } dp[cur][sum] = 1; return sum; } int a, b; int main() { rep(i, 2005) dp[i].resize(2005, 0); cin >> N >> K; while (cin >> a >> b) { G[a].push_back(b); G[b].push_back(a); } dfs(0, -1); #if 0 rep(i, 5) rep(j, 5) { printf("%d%c", dp[i][j], j == 5-1 ? '\n' : ' '); } #endif cout << dp[0][K] << endl; return 0; }