結果
問題 | No.196 典型DP (1) |
ユーザー | Pachicobue |
提出日時 | 2017-08-09 19:14:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 86 ms / 2,000 ms |
コード長 | 4,354 bytes |
コンパイル時間 | 1,893 ms |
コンパイル使用メモリ | 176,848 KB |
実行使用メモリ | 97,920 KB |
最終ジャッジ日時 | 2024-10-12 04:01:55 |
合計ジャッジ時間 | 3,964 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
// {{{ Templates #include <bits/stdc++.h> #define show(x) cerr << #x << " = " << x << endl using namespace std; using ll = long long; using pii = pair<int, int>; using vi = vector<int>; template <typename T> ostream& operator<<(ostream& os, const vector<T>& v) { os << "sz:" << v.size() << "\n["; for (const auto& p : v) { os << p << ","; } os << "]\n"; return os; } template <typename S, typename T> ostream& operator<<(ostream& os, const pair<S, T>& p) { os << "(" << p.first << "," << p.second << ")"; return os; } constexpr ll MOD = (ll)1e9 + 7LL; template <typename T> constexpr T INF = numeric_limits<T>::max() / 100; // }}} constexpr int MAX = 2000; int N; int K; struct Graph { Graph(const int n) { edge.resize(n); } void addEdge(const int from, const int to) { edge[from].push_back(to); } vector<vector<int>> edge; }; struct Polynomial { Polynomial() : degree(0) { fill(coeff, coeff + MAX + 1, 0); } static Polynomial monomial(const ll coe, const int deg) { Polynomial p; p.coeff[deg] = coe; p.degree = deg; return p; } Polynomial operator+(const Polynomial& p) const { Polynomial P; if (degree >= p.degree) { for (int i = 0; i <= p.degree; i++) { P.coeff[i] = (coeff[i] + p.coeff[i]) % MOD; } } else { for (int i = 0; i <= degree; i++) { P.coeff[i] = (coeff[i] + p.coeff[i]) % MOD; } for (int i = degree + 1; i <= p.degree; i++) { P.coeff[i] = p.coeff[i]; } } P.degree = max(degree, p.degree); return (*this); } Polynomial& operator+=(const Polynomial& p) { if (degree >= p.degree) { for (int i = 0; i <= p.degree; i++) { coeff[i] += p.coeff[i]; coeff[i] = coeff[i] % MOD; } } else { for (int i = 0; i <= degree; i++) { coeff[i] += p.coeff[i]; coeff[i] = coeff[i] % MOD; } for (int i = degree + 1; i <= p.degree; i++) { coeff[i] = p.coeff[i]; coeff[i] = coeff[i] % MOD; } } degree = max(degree, p.degree); return (*this); } Polynomial operator*(const Polynomial& p) const { Polynomial P; P.degree = degree + p.degree; for (int i = 0; i <= degree; i++) { for (int j = 0; j <= p.degree; j++) { P.coeff[i + j] += coeff[i] * p.coeff[j]; P.coeff[i + j] = P.coeff[i + j] % MOD; } } return P; } int degree = 0; ll coeff[MAX + 1]; }; ostream& operator<<(ostream& os, const Polynomial& p) { for (int i = 0; i <= p.degree; i++) { if (i > 0) { os << " + "; } os << p.coeff[i]; if (i > 0) { os << "x^" << i; } } os << endl; return os; } void direct_dfs(const Graph& g_, Graph& g, const int s, vector<bool>& visited) { visited[s] = true; for (const int to : g_.edge[s]) { if (not visited[to]) { visited[to] = true; g.addEdge(s, to); direct_dfs(g_, g, to, visited); } } } int size_dfs(const Graph& g, const int s, vector<int>& size) { int num = 1; for (const int to : g.edge[s]) { num += size_dfs(g, to, size); } size[s] = num; return num; } Polynomial dp_dfs(const Graph& g, const int s, const vector<int>& size) { Polynomial P = Polynomial::monomial(1LL, size[s]); Polynomial Product = Polynomial::monomial(1LL, 0); for (const int to : g.edge[s]) { Product = Product * dp_dfs(g, to, size); } P += Product; return P; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N >> K; Graph g_(N); for (int i = 0; i < N - 1; i++) { int a, b; cin >> a >> b; g_.addEdge(a, b); g_.addEdge(b, a); } Graph g(N); vector<bool> visited(N, false); direct_dfs(g_, g, 0, visited); vector<int> size(N, 0); size_dfs(g, 0, size); cout << dp_dfs(g, 0, size).coeff[K] << endl; return 0; }