結果

問題 No.196 典型DP (1)
コンテスト
ユーザー pekempey
提出日時 2015-10-23 16:26:27
言語 C++11（廃止可能性あり）
(gcc 13.3.0 + boost 1.89.0)
結果
TLE  
実行時間 -
コード長 3,694 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,186 ms
コンパイル使用メモリ 174,624 KB
実行使用メモリ 49,240 KB
最終ジャッジ日時 2024-07-22 11:33:07
合計ジャッジ時間 11,785 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 11 TLE * 2 -- * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#define GET_MACRO(a, b, c, NAME, ...) NAME
#define rep(...) GET_MACRO(__VA_ARGS__, rep3, rep2)(__VA_ARGS__)
#define rep2(i, a) rep3 (i, 0, a)
#define rep3(i, a, b) for (int i = (a); i < (b); i++)
#define repr(...) GET_MACRO(__VA_ARGS__, repr3, repr2)(__VA_ARGS__)
#define repr2(i, a) repr3 (i, 0, a)
#define repr3(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define chmin(a, b) ((b) < a && (a = (b), true))
#define chmax(a, b) (a < (b) && (a = (b), true))
using namespace std;
typedef long long ll;

vector<int> G[2020];
vector<ll> dp[2020];
int size[2020];
const ll mod = 1e9 + 7;

pair<ll, ll> extgcd(ll a, ll b) {
	if (b == 0) return make_pair(1, 0);
	auto p = extgcd(b, a % b);
	return make_pair(p.second, p.first - a / b * p.second);
}

ll modulo(ll a, ll mod) {
	a %= mod; a += mod; a %= mod;
	return a;
}

ll modpow(ll a, ll b, ll mod) {
	ll res = 1;
	while (b) {
		if (b & 1) (res *= a) %= mod;
		(a *= a) %= mod;
		b /= 2;
	}
	return res;
}

ll modinv(ll a, ll mod) {
	if (a == 0) return -1;
	if (__gcd(a, mod) != 1) return -1;
	return modulo(extgcd(a, mod).first, mod);
}

ll garner(vector<pair<ll, ll>> eq, ll mod) {
	eq.emplace_back(0, mod);
	int n = eq.size();
	vector<ll> coef(n, 1), sum(n, 0);
	rep (i, n - 1) {
		ll v = (eq[i].first - sum[i]) * modinv(coef[i], eq[i].second) % eq[i].second;
		if (v < 0) v += eq[i].second;
		rep (j, i + 1, n) {
			(sum[j] += coef[j] * v) %= eq[j].second;
			(coef[j] *= eq[i].second) %= eq[j].second;
		}
	}
	return sum.back();
}

struct NTT {
	ll mod, root;
	NTT() {}
	NTT(ll mod, ll root) : mod(mod), root(root) {}
	vector<ll> ntt(vector<ll> a, int sign) {
		int n = a.size();
		ll base = modpow(root, (mod - 1) / n, mod);
		if (sign == -1) base = modinv(base, mod);
		for (int m = n; m >= 2; m >>= 1) {
			int mh = m >> 1;
			ll w = 1;
			for (int i = 0; i < mh; i++) {
				for (int j = i; j < n; j += m) {
					int k = j + mh;
					ll x = (a[j] - a[k] + mod) % mod;
					a[j] = (a[j] + a[k]) % mod;
					a[k] = w * x % mod;
				}
				w = w * base % mod;
			}
			base = base * base % mod;
		}
		int i = 0;
		for (int j = 1; j < n - 1; j++) {
			for (int k = n >> 1; k > (i ^= k); k >>= 1);
			if (j > i) swap(a[i], a[j]);
		}
		if (sign == -1) {
			ll inv = modinv(n, mod);
			rep (i, n) a[i] = a[i] * inv % mod;
		}
		return a;
	}
	vector<ll> convolution(vector<ll> a, vector<ll> b) {
		a = ntt(a, 1);
		b = ntt(b, 1);
		rep (i, a.size()) (a[i] *= b[i]) %= mod;
		a = ntt(a, -1);
		return a;
	}
};

vector<ll> convolution(vector<ll> a, vector<ll> b, ll mod) {
	int size = 1;
	int n = a.size() + b.size() + 1;
	while (size < n) size *= 2;
	a.resize(size); b.resize(size);
	for (auto &x : a) x %= mod;
	for (auto &x : b) x %= mod;
	ll m[] = {1224736769, 469762049, 167772161};
	ll r[] = {3, 3, 3};
	const int N = 3;
	NTT ntt[N];
	rep (i, N) ntt[i] = NTT(m[i], r[i]);
	vector<ll> cs[N];
	rep (i, N) cs[i] = ntt[i].convolution(a, b);
	vector<ll> res(a.size());
	vector<pair<ll, ll>> eq(N);
	rep (i, res.size()) {
		rep (j, N) eq[j] = make_pair(cs[j][i], ntt[j].mod);
		res[i] = garner(eq, mod);
	}
	res.resize(n);
	return res;
}

int dfs2(int curr, int prev) {
	size[curr] = 1;
	for (int next : G[curr]) if (next != prev) {
		size[curr] += dfs2(next, curr);
	}
	return size[curr];
}

void dfs(int curr, int prev) {
	dp[curr][0] = 1;
	for (int next : G[curr]) if (next != prev) {
		dfs(next, curr);	
		dp[curr] = convolution(dp[curr], dp[next], mod);
	}
	dp[curr][size[curr]] = 1;
}

int main() {
	int N, K;
	cin >> N >> K;
	rep (i, 2020) dp[i].resize(2020);
	rep (i, N - 1) {
		int u, v;
		cin >> u >> v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs2(0, -1);
	dfs(0, -1);
	cout << dp[0][K] << endl;
	return 0;
}
0