結果
問題 | No.1227 I hate ThREE |
ユーザー |
![]() |
提出日時 | 2020-12-17 18:53:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 194 ms / 2,000 ms |
コード長 | 1,939 bytes |
コンパイル時間 | 1,731 ms |
コンパイル使用メモリ | 117,644 KB |
実行使用メモリ | 50,500 KB |
最終ジャッジ日時 | 2024-09-21 08:12:29 |
合計ジャッジ時間 | 6,033 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#pragma GCC target("avx2")#pragma GCC optimize("O3")#pragma GCC optimize("unroll-loops")#include <algorithm>#include <bitset>#include <climits>#include <cmath>#include <cstring>#include <deque>#include <forward_list>#include <iomanip>#include <iostream>#include <list>#include <map>#include <queue>#include <set>#include <string>#include <unordered_map>#include <unordered_set>#include <utility>#include <vector>using namespace std;typedef long long ll;typedef pair<int, int> P;typedef bitset<16> BS;const ll MOD = 1E+09 + 7;const ll INF = 1E18;const int MAX_N = 1000;ll N, C;ll dp[MAX_N + 1][6 * MAX_N];vector<ll> G[MAX_N];ll tree(ll i, ll par, ll j);ll modPow(ll x, ll a);int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cin >> N >> C;for (int i = 1; i <= N - 1; i++) {ll a, b;cin >> a >> b;G[a].push_back(b);G[b].push_back(a);}fill(dp[0], dp[N + 1], -1);ll ans = 0;for (int i = 1; i <= min(C, 6 * N - 5); i++) {ans += tree(1, 0, i);ans %= MOD;}ans += (modPow(2, N - 1) * max(0LL, C - 6 * N + 5)) % MOD;ans %= MOD;/*for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {cout << "i = " << i << ", j = " << j << ", dp = " << dp[i][j] << "\n";}}*/cout << ans << "\n";return 0;}ll tree(ll i, ll par, ll j){if (j < 1 || j > min(C, 6 * N - 5))return 0;if (dp[i][j] != -1)return dp[i][j];ll res = 1;for (auto c : G[i]) {if (c != par) {res *= (tree(c, i, j + 3) + tree(c, i, j - 3)) % MOD;res %= MOD;}}return dp[i][j] = res;}ll modPow(ll x, ll a){ll ans = 1;while (a > 0) {if (a & 1) {ans = (ans * x) % MOD;}x = (x * x) % MOD;a >>= 1;}return ans;}