結果
問題 | No.196 典型DP (1) |
ユーザー | 🍮かんプリン |
提出日時 | 2020-10-13 21:39:27 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 117 ms / 2,000 ms |
コード長 | 11,179 bytes |
コンパイル時間 | 3,883 ms |
コンパイル使用メモリ | 213,244 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 18:48:52 |
合計ジャッジ時間 | 6,902 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
/*** @FileName a.cpp* @Author kanpurin* @Created 2020.10.13 21:39:21**/#include "bits/stdc++.h"using namespace std;typedef long long ll;template< int MOD >struct mint {public:long long x;mint(long long x = 0) :x((x%MOD+MOD)%MOD) {}mint(std::string &s) {long long z = 0;for (int i = 0; i < s.size(); i++) {z *= 10;z += s[i] - '0';z %= MOD;}this->x = z;}mint& operator+=(const mint &a) {if ((x += a.x) >= MOD) x -= MOD;return *this;}mint& operator-=(const mint &a) {if ((x += MOD - a.x) >= MOD) x -= MOD;return *this;}mint& operator*=(const mint &a) {(x *= a.x) %= MOD;return *this;}mint& operator/=(const mint &a) {long long n = MOD - 2;mint u = 1, b = a;while (n > 0) {if (n & 1) {u *= b;}b *= b;n >>= 1;}return *this *= u;}mint operator+(const mint &a) const {mint res(*this);return res += a;}mint operator-() const {return mint() -= *this; }mint operator-(const mint &a) const {mint res(*this);return res -= a;}mint operator*(const mint &a) const {mint res(*this);return res *= a;}mint operator/(const mint &a) const {mint res(*this);return res /= a;}friend std::ostream& operator<<(std::ostream &os, const mint &n) {return os << n.x;}friend std::istream &operator>>(std::istream &is, mint &n) {long long x;is >> x;n = mint(x);return is;}bool operator==(const mint &a) const {return this->x == a.x;}mint pow(long long k) const {mint ret = 1;mint p = this->x;while (k > 0) {if (k & 1) {ret *= p;}p *= p;k >>= 1;}return ret;}};constexpr int MOD = 1e9 + 7;template < const int MOD , bool any = false>struct FormalPowerSeries {private:using P = FormalPowerSeries< MOD, any >;template < class T, class F = multiplies< T > >T power(T a, long long n, F op = multiplies< T >(), T e = {1}) const {assert(n >= 0);T res = e;while (n) {if (n & 1) res = op(res, a);if (n >>= 1) a = op(a, a);}return res;}template< int _MOD >void ntt(vector< mint < _MOD > >& a, bool inverse) {static vector< mint< _MOD > > dw(30), idw(30);if (dw[0] == 0) {mint< _MOD > root = 2;while (power(root, (_MOD - 1) / 2) == 1) root += 1;for (int i = 0; i < 30; i++) dw[i] = -power(root, (_MOD - 1) >> (i + 2)), idw[i] = mint<_MOD>(1) / dw[i];}int n = a.size();assert((n & (n - 1)) == 0);if (not inverse) {for (int m = n; m >>= 1;) {mint< _MOD > w = 1;for (int s = 0, k = 0; s < n; s += 2 * m) {for (int i = s, j = s + m; i < s + m; i++, j++) {auto x = a[i], y = a[j] * w;if (x.x >= _MOD) x.x -= _MOD;a[i].x = x.x + y.x, a[j].x = x.x + (_MOD - y.x);}w *= dw[__builtin_ctz(++k)];}}} else {for (int m = 1; m < n; m *= 2) {mint< _MOD > w = 1;for (int s = 0, k = 0; s < n; s += 2 * m) {for (int i = s, j = s + m; i < s + m; i++, j++) {auto x = a[i], y = a[j];a[i] = x + y, a[j].x = x.x + (_MOD - y.x), a[j] *= w;}w *= idw[__builtin_ctz(++k)];}}}auto c = mint<_MOD>(1) / mint< _MOD >(inverse ? n : 1);for (auto&& e : a) e *= c;}template< int _MOD >vector< mint< _MOD > > convolution(vector< mint< _MOD > > l, vector< mint< _MOD > > r) {if (l.empty() || r.empty()) return {};int n = l.size(), m = r.size(), sz = 1 << __lg(2 * (n + m - 1) - 1);if (min(n, m) < 30) {vector< long long > res(n + m - 1);for (int i = 0; i < n; i++)for (int j = 0; j < m; j++) res[i + j] += (l[i] * r[j]).x;return {begin(res), end(res)};}bool eq = l == r;l.resize(sz), ntt(l, false);if (eq) r = l;else r.resize(sz), ntt(r, false);for (int i = 0; i < sz; i++) l[i] *= r[i];ntt(l, true), l.resize(n + m - 1);return l;}P pre(const P &p, int sz) const {P ret;ret.a = vector<mint<MOD>>(p.a.begin(), p.a.begin() + min((int)p.a.size(), sz));return ret;}public:vector<mint<MOD>> a;FormalPowerSeries(int sz = 0) {this->a.resize(sz, 0);}FormalPowerSeries(std::initializer_list<mint<MOD>> v) {this->a = v;}P resize(int k) const {return pre(*this,k);}size_t size() const { return this->a.size(); }bool operator<(const P& r) const { return this->a.size() < r.a.size(); }bool operator>(const P& r) const { return this->a.size() > r.a.size(); }P operator+(const P &a) const { return P(*this) += a; }P operator+(const long long a) const { return P(*this) += a; }P operator-(const P &a) const { return P(*this) -= a; }P operator*(const P &a) const { return P(*this) *= a; }P operator*(const long long a) const { return P(*this) *= a; }P operator/(const P &a) const { return P(*this) /= a; }P &operator+=(const P &r) {this->a.resize(max(this->a.size(),r.size()));for(int i = 0; i < (int)r.size(); i++) this->a[i] += r.a[i];return *this;}P &operator+=(const long long v) {if (this->a.size() == 0) this->a.resize(1,(v % MOD + MOD) % MOD);else this->a[0] += v;return *this;}P &operator-=(const P &r) {this->a.resize(max(this->a.size(),r.size()));for(int i = 0; i < (int)r.size(); i++) this->a[i] -= r.a[i];return *this;}P &operator*=(const P &b) {if (!any) {this->a = convolution(this->a, b.a);return *this;}else {if (this->a.empty() || b.a.empty()) {this->a.clear();return *this;}int n = this->a.size(), m = b.a.size();static constexpr int mod0 = 998244353, mod1 = 1300234241, mod2 = 1484783617;using Mint0 = mint< mod0 >;using Mint1 = mint< mod1 >;using Mint2 = mint< mod2 >;vector< Mint0 > l0(n), r0(m);vector< Mint1 > l1(n), r1(m);vector< Mint2 > l2(n), r2(m);for (int i = 0; i < n; i++) l0[i] = this->a[i].x, l1[i] = this->a[i].x, l2[i] = this->a[i].x;for (int j = 0; j < m; j++) r0[j] = b.a[j].x, r1[j] = b.a[j].x, r2[j] = b.a[j].x;l0 = convolution(l0,r0);l1 = convolution(l1,r1);l2 = convolution(l2,r2);this->a.resize(n + m - 1);static const Mint1 im0 = Mint1(1) / Mint1(mod0);static const Mint2 im1 = Mint2(1) / Mint2(mod1), im0m1 = im1 / mod0;static const mint<MOD> m0 = mod0, m0m1 = m0 * mod1;for (int i = 0; i < n + m - 1; i++) {int y0 = l0[i].x;int y1 = (im0 * (l1[i] - y0)).x;int y2 = (im0m1 * (l2[i] - y0) - im1 * y1).x;this->a[i] = m0m1 * y2 + y0 + m0 * y1;}return *this;}}P &operator*=(const long long v) {for (int i = 0; i < this->a.size(); i++) this->a[i] *= v;return *this;}P &operator/=(const P &a) {*this *= a.inverse();return *this;}P inverse(int deg = -1) const {assert(this->a.size() != 0 && this->a[0].x != 0);const int n = (int)this->a.size();if(deg == -1) deg = n;P ret(1);ret[0] = mint<MOD>(1) / a[0];for(int i = 1; i < deg; i <<= 1) {ret = pre((ret + ret - ret * ret * pre(*this,i << 1)),i << 1);}return pre(ret,deg);}P differential() const {const int n = (int) this->a.size();P ret(max(0, n - 1));for(int i = 1; i < n; i++) ret[i-1] = this->a[i] * i;return ret;}P integral() const {const int n = (int) this->a.size();P ret(n + 1);for(int i = 0; i < n; i++) ret[i + 1] = this->a[i] / (i + 1);return ret;}P log(int deg = -1) const {assert(this->a.size() != 0 && this->a[0] == 1);const int n = (int)this->a.size();if(deg == -1) deg = n;return pre((this->differential() * this->inverse(deg)),deg - 1).integral();}P exp(int deg = -1) const {if (this->a.size() == 0) return P(0);assert(this->a[0] == 0);const int n = (int)this->a.size();if(deg == -1) deg = n;P ret(1);ret.a[0] = 1;for(int i = 1; i < deg; i <<= 1) {ret = pre((ret * (pre(*this,i << 1) + 1 - ret.log(i << 1))),i << 1);}return pre(ret,deg);}P pow(long long k, int deg = -1) const {const int n = (int) this->a.size();if(deg == -1) deg = n;for(int i = 0; i < n; i++) {if(this->a[i].x != 0) {long long rev = (mint<MOD>(1) / this->a[i]).x;P C = *this * rev;P D(n - i);for(int j = i; j < n; j++) D[j - i] = C[j];D = (D.log() * k).exp() * power(this->a[i], k).x;P E(deg);if(i * k > deg) return E;auto S = i * k;for(int j = 0; j + S < deg && j < D.size(); j++) E[j + S] = D[j];return E;}}return *this;}mint< MOD > &operator[](int x) {assert(0 <= x && x < (int)this->a.size());return a[x];}friend std::ostream &operator<<(std::ostream &os, const P &p) {os << "[ ";for (int i = 0; i < p.size(); ++i) {os << p.a[i] << " ";}os << "]";return os;}};vector<vector<int>> g;FormalPowerSeries<MOD,true> dfs(int v, int p = -1) {FormalPowerSeries<MOD,true> ret({1});for(int u : g[v]) {if (u == p) continue;ret *= dfs(u,v);}FormalPowerSeries<MOD,true> tmp(ret.size()+1);tmp[ret.size()] += 1;ret += tmp;return ret;}int main() {int n,k;cin >> n >> k;g.resize(n);for (int i = 0; i < n-1; i++) {int a,b;cin >> a >> b;g[a].push_back(b);g[b].push_back(a);}auto ans = dfs(0);cout << ans[k] << endl;return 0;}