Advertisement
Guest User

Untitled

a guest
Mar 24th, 2019
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.24 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #define _USE_MATH_DEFINES
  3.  
  4. #include <iostream>
  5. #include <fstream>
  6. #include <stdio.h>
  7. #include <string>
  8. #include <vector>
  9. #include <cmath>
  10. #include <algorithm>
  11. #include <set>
  12. #include <map>
  13. #include <ctime>
  14. #include <cstring>
  15. #include <iomanip>
  16. #include <random>
  17. #include <unordered_set>
  18. #include <unordered_map>
  19. #include <deque>
  20. #include <queue>
  21. #include <bitset>
  22. #include <sstream>
  23. #include <cassert>
  24. #include <complex>
  25.  
  26. using namespace std;
  27.  
  28. #define mp make_pair
  29. #define X first
  30. #define Y second
  31. #define all(x) x.begin(), x.end()
  32. #define all_(x) x.rbegin(), x.rend()
  33. #define multi_test 0
  34.  
  35. typedef unsigned int ui;
  36. typedef long long ll;
  37. typedef unsigned long long ull;
  38. typedef long double ld;
  39. typedef pair<ll, ll> pll;
  40. typedef pair<int, int> pii;
  41. typedef pair<ld, ld> pld;
  42. typedef complex<ld> base;
  43.  
  44. const int INF = 2e9 + 9;
  45. const ll INF1 = 8e18 + 9;
  46. const ll MAXN = 3e5 + 7;
  47. const ll MAXN1 = 1 << 10;
  48. const ll MAXN2 = 55 * MAXN;
  49. const ll MOD = 998244353;
  50. const ll MOD1 = 1e9 + 9;
  51. const ll ALPH = 27;
  52. const ll PW1 = 2;
  53. const ll PW2 = 199;
  54. const ll PW3 = 193;
  55. const ll PW4 = 117;
  56. const ld EPS = 1e-7;
  57. const ll BLOCK = 316;
  58. const ll BLOCK1 = 1 << 9;
  59. const ull T = 3e9 + 239;
  60.  
  61. void solve();
  62.  
  63. signed main(){
  64.     srand('a' + 'l' + 'e' + 'x' + 'X' + '5' + '1' + '2');
  65.     ios_base::sync_with_stdio(0);
  66.     cin.tie(0);
  67.     cout.tie(0);
  68. #ifdef _DEBUG
  69. #define MAXN 5000
  70.     freopen("input.txt", "r", stdin);
  71.     freopen("output.txt", "w", stdout);
  72. #endif // _DEBUG
  73.     int q = 1;
  74.     if (multi_test) cin >> q;
  75.     while (q--) solve();
  76. }
  77.  
  78. /*------------------------------------------------------------------------------------------------------------*/
  79.  
  80.  
  81. vector<pii> g[MAXN];
  82. ll dp[MAXN1][MAXN1], tmp[MAXN1][MAXN1], cnt[MAXN1], c[MAXN1][MAXN1];
  83. ll fc[MAXN];
  84.  
  85. ll bin_pow(ll a, ll k) {
  86.     if (k == 0) return 1;
  87.     if (k % 2 == 0) return bin_pow(a * a % MOD, k / 2);
  88.     return (bin_pow(a, k - 1) * a) % MOD;
  89. }
  90.  
  91. ll inv(ll x) {
  92.     return bin_pow(x, MOD - 2);
  93. }
  94.  
  95. ll f(ll x, ll y) {
  96.     return c[x + y][x];
  97. }
  98.  
  99. void add(ll &a, ll b) {
  100.     a = (a + b) % MOD;
  101. }
  102.  
  103. ll mult(ll a, ll b) {
  104.     return (a * b) % MOD;
  105. }
  106.  
  107. void dfs(int vert, int p = -1) {
  108.     dp[vert][0] = 1;
  109.     cnt[vert] = 1;
  110.     for (auto &i : g[vert]) {
  111.         if (i.X == p) continue;
  112.         dfs(i.X, vert);
  113.         for (int j = 0; j < cnt[vert] + cnt[i.X]; ++j) {
  114.             tmp[vert][j] = 0;
  115.             for (int a = 0; a < min<ll>(cnt[vert], j + 1); ++a) {
  116.                 if (i.Y == 1) {
  117.                     for (int b = j - a; b < cnt[i.X]; ++b) {
  118.                         add(tmp[vert][j], mult(mult(mult(dp[vert][a], dp[i.X][b]), f(a, j - a)), f(cnt[vert] - a - 1, cnt[i.X] - j + a)));
  119.                     }
  120.                 }
  121.                 else {
  122.                     for (int b = 0; b < j - a; ++b) {
  123.                         add(tmp[vert][j], mult(mult(mult(dp[vert][a], dp[i.X][b]), f(a, j - a)), f(cnt[vert] - a - 1, cnt[i.X] - j + a)));
  124.                     }
  125.                 }
  126.             }
  127.         }
  128.         for (int j = 0; j < cnt[vert] + cnt[i.X]; ++j) {
  129.             dp[vert][j] = tmp[vert][j];
  130.         }
  131.         cnt[vert] += cnt[i.X];
  132.     }
  133. }
  134.  
  135. void solve() {
  136.     fc[0] = 1;
  137.     for (ll i = 1; i < MAXN; ++i) fc[i] = (fc[i - 1] * i) % MOD;
  138.     for (int i = 0; i < MAXN1; ++i) {
  139.         for (int j = 0; j <= i; ++j) {
  140.             c[i][j] = fc[i] * inv(fc[i - j] * fc[j] % MOD) % MOD;
  141.         }
  142.     }
  143.     int n;
  144.     cin >> n;
  145.     for (int i = 1; i < n; ++i) {
  146.         int a, b;
  147.         cin >> a >> b;
  148.         g[a].emplace_back(b, 1);
  149.         g[b].emplace_back(a, 0);
  150.     }
  151.     dfs(1);
  152.     ll ans = 0;
  153.     for (int i = 0; i < n; ++i) add(ans, dp[1][i]);
  154.     cout << ans;
  155. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement