結果
問題 | No.196 典型DP (1) |
ユーザー | kura197 |
提出日時 | 2022-01-01 16:42:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 275 ms / 2,000 ms |
コード長 | 1,977 bytes |
コンパイル時間 | 2,302 ms |
コンパイル使用メモリ | 201,372 KB |
最終ジャッジ日時 | 2025-01-27 08:18:35 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define REP(i, n) for(int i=0; i<n; i++) #define REPi(i, a, b) for(int i=int(a); i<int(b); i++) #define MEMS(a,b) memset(a,b,sizeof(a)) #define mp make_pair #define MOD(a, m) ((a % m + m) % m) template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; } const ll MOD = 1e9+7; vector<int> G[2100]; using vec1 = vector<ll>; using vec2 = vector<vec1>; using vec3 = vector<vec2>; vec2 dfs(int v, int p){ vec2 dp(2, vec1(2)); dp[0][0] = 1; dp[1][1] = 1; for(auto& nv : G[v]){ if(nv == p) continue; auto ndp = dfs(nv, v); int sz_v = dp.size(); int sz_nv = ndp.size(); vec2 dp_v(sz_v + sz_nv, vec1(2)); swap(dp_v, dp); REP(k0, sz_v){ REP(k1, sz_nv){ REP(j0, 2){ REP(j1, 2){ if(dp_v[k0][j0] == 0) continue; if(ndp[k1][j1] == 0) continue; auto val = (dp_v[k0][j0] * ndp[k1][j1]) % MOD; int ni = k0+k1; int nj = -1; //if(j0 == 1 && j1 == 1) nj = 1; //else nj = 0; if(j0 == 1){ if(j1 == 1) nj = 1; else continue; } else nj = 0; dp[ni][nj] += val; dp[ni][nj] %= MOD; } } } } } return dp; } int main(){ int N, K; cin >> N >> K; REP(i,N-1){ int a, b; cin >> a >> b; G[a].push_back(b); G[b].push_back(a); } auto dp = dfs(0, -1); ll ans = dp[K][0] + dp[K][1]; cout << ans % MOD << endl; return 0; }