Dang_Quan_10_Tin

PVHOI 2021 tree

Oct 17th, 2021 (edited)
221
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #define task "tree"
  2.  
  3. #include <iostream>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <algorithm>
  7. #include <functional>
  8.  
  9. using namespace std;
  10.  
  11. using ll = long long;
  12. using ld = long double;
  13.  
  14. constexpr int N = 1e6 + 5;
  15. ll Pow(ll a, ll b, ll mod);
  16. ll mod, p;
  17.  
  18. pair<ll, int> gt[N], rgt[N];
  19.  
  20. int n, k;
  21. int cnt[N];
  22. vector<int> adj[N];
  23.  
  24. void Read()
  25. {
  26.     cin >> n >> k >> p;
  27.     for (int i = 1; i < n; ++i)
  28.     {
  29.         int u, v;
  30.         cin >> u >> v;
  31.         adj[u].emplace_back(v);
  32.         adj[v].emplace_back(u);
  33.     }
  34. }
  35.  
  36. ll C(int k, int n)
  37. {
  38.     if (k > n)
  39.         return 0;
  40.     if (gt[n].second + rgt[k].second + rgt[n - k].second > 0)
  41.         return 0;
  42.     return gt[n].first * rgt[k].first % mod * rgt[n - k].first % mod;
  43. }
  44.  
  45. ll Cal(ll mods)
  46. {
  47.     mod = mods;
  48.     rgt[0] = gt[0] = make_pair(1, 0);
  49.  
  50.     for (int i = 1; i <= n; ++i)
  51.     {
  52.         ll v = i;
  53.         gt[i] = gt[i - 1];
  54.         rgt[i] = rgt[i - 1];
  55.  
  56.         while (v % mod == 0)
  57.         {
  58.             v /= mod;
  59.             ++gt[i].second;
  60.             --rgt[i].second;
  61.         }
  62.  
  63.         (gt[i].first *= v) %= mod;
  64.         rgt[i].first = v;
  65.     }
  66.     for (int i = 1; i <= n; ++i)
  67.         rgt[i].first = rgt[i + 1].first;
  68.  
  69.     rgt[n].first = Pow(gt[n].first, mod - 2, mod);
  70.     for (int i = n - 1; i; --i)
  71.         (rgt[i].first *= rgt[i + 1].first) %= mod;
  72.  
  73.     ll ans(0);
  74.  
  75.     function<void(int, int)> GetAns = [&](int v, int p)
  76.     {
  77.         (ans += C(k, n - 1)) %= mod;
  78.         cnt[v] = 1;
  79.  
  80.         for (auto i : adj[v])
  81.             if (i != p)
  82.             {
  83.                 GetAns(i, v);
  84.                 cnt[v] += cnt[i];
  85.                 (ans -= C(k, cnt[i])) %= mod;
  86.             }
  87.  
  88.         (ans -= C(k, n - cnt[v])) %= mod;
  89.     };
  90.  
  91.     GetAns(1, -1);
  92.  
  93.     return (ans + mod) % mod;
  94. }
  95.  
  96. void Sub_n()
  97. {
  98.     if (p == 1019972207)
  99.         cout << Cal(p);
  100.     else
  101.     {
  102.         ll a1 = Cal(19),
  103.            a2 = Cal(127),
  104.            a3 = Cal(467),
  105.            a4 = Cal(907);
  106.  
  107.         ll m1 = p / 19,
  108.            m2 = p / 127,
  109.            m3 = p / 467,
  110.            m4 = p / 907;
  111.  
  112.         cout << (a1 * m1 * Pow(m1, 17, 19) + a2 * m2 * Pow(m2, 125, 127) + a3 * m3 * Pow(m3, 465, 467) + a4 * m4 * Pow(m4, 905, 907)) % p;
  113.     }
  114. }
  115.  
  116. int32_t main()
  117. {
  118.     ios::sync_with_stdio(0);
  119.     cin.tie(0);
  120.     cout.tie(0);
  121.     if (fopen(task ".INP", "r"))
  122.     {
  123.         freopen(task ".INP", "r", stdin);
  124.         freopen(task ".OUT", "w", stdout);
  125.     }
  126.     Read();
  127.     Sub_n();
  128. }
  129.  
  130. ll Pow(ll a, ll b, ll mod)
  131. {
  132.     ll ans(1);
  133.     for (; b > 0; b >>= 1)
  134.     {
  135.         if (b & 1)
  136.             ans = ans * a % mod;
  137.         a = a * a % mod;
  138.     }
  139.     return ans;
  140. }
RAW Paste Data