Advertisement
BaoJIaoPisu

Untitled

Oct 21st, 2021
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.74 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define pb push_back
  5. #define pf push_front
  6. #define popb pop_back
  7. #define popf pop_front
  8. #define ins insert
  9. #define pq priority_queue
  10. #define minele min_element
  11. #define maxele max_element
  12. #define lb lower_bound //first pos >= val
  13. #define ub upper_bound // first pos > val
  14. #define cnt_bit __builtin_popcount
  15. #define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
  16. //#pragma GCC optimize("Ofast")
  17. //#pragma GCC target("avx,avx2,fma")
  18. using namespace std;
  19.  
  20. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  21.  
  22. typedef long long ll;
  23. typedef pair<ll, ll> pll;
  24. typedef pair<int, int> pii;
  25.  
  26.  
  27. int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
  28. int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
  29. int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};
  30.  
  31. const ll oo = 1e18;
  32. const ll maxN = 1e6;
  33.  
  34. /* Author : Le Ngoc Bao Anh, 10A5, LQD High School for Gifted Student */
  35.  
  36. void maximize(int &a, int b) {
  37.     a = max(a, b);
  38. }
  39.  
  40. void minimize(int &a, int b) {
  41.     a = min(a, b);
  42. }
  43.  
  44. ll MOD;
  45. const int N = 1e6 + 100;
  46. int n, k;
  47. int sz[N];
  48. int cnt[4][N], num[N];
  49. ll f[N], invf[N], fact[N], ans[N];
  50. vector<int> g[N];
  51. vector<int> b[N];
  52.  
  53. ll Power(ll a, ll b, ll MOD) {
  54.     if(b == 0) return 1;
  55.     if(b == 1) return (a % MOD);
  56.     ll T = Power(a, b / 2, MOD);
  57.     if(b % 2) return (T * T % MOD * a % MOD);
  58.     return (T * T % MOD);
  59. }
  60.  
  61. int phi(int n) {
  62.     int res = n;
  63.     for (int i = 2; i * i <= n; ++i) {
  64.         if (n % i == 0) {
  65.             while (n % i == 0) {
  66.                 n /= i;
  67.             }
  68.             res -= res / i;
  69.         }
  70.     }
  71.     if (n != 1) {
  72.         res -= res / n;
  73.     }
  74.     return res;
  75. }
  76.  
  77. void add(ll &x, ll y) {
  78.     x = (x + y);
  79.     if(x < 0) x += MOD;
  80.     if(x >= MOD) x -= MOD;
  81. }
  82.  
  83. void dfs(int u, int p) {
  84.     sz[u] = 1;
  85.     ans[u] = f[n - 1];
  86.     for(auto v : g[u]) {
  87.         if(v != p) {
  88.             dfs(v, u);
  89.             sz[u] += sz[v];
  90.             add(ans[u], -f[sz[v]]);
  91.         }
  92.     }
  93.     add(ans[u], -f[n - sz[u]]);
  94. }
  95.  
  96. void solve() {
  97.     //ans(u) = C(n - 1, k) - (v is son of u)C(chils(v), k) - C(n - child(u), k);
  98.     //=> how to cal C(x, k)
  99.     //C(x, k) = C(x - 1, k) * x / (x - k);
  100.     //=> gcd(x, y) = 1 => x * c mod y = 1 (c = phi(y))
  101.     cin >> n >> k >> MOD;
  102.  
  103.     for(int i = 1; i < n; i++) {
  104.         int u, v;
  105.         cin >> u >> v;
  106.         g[u].pb(v);
  107.         g[v].pb(u);
  108.     }
  109.  
  110.     if(MOD == 1019972207) {
  111.         fact[0] = 1;
  112.         invf[0] = 1;
  113.         for(int i = 1; i <= n; i++) {
  114.             fact[i] = fact[i - 1] * i % MOD;
  115.             invf[i] = Power(fact[i], MOD - 2, MOD);
  116.         }
  117.  
  118.         for(int i = k; i <= n; i++) {
  119.             f[i] = fact[i] * invf[k] % MOD * invf[i - k] % MOD;
  120.         }
  121.     } else {
  122.         vector<int> prime = {19, 127, 467, 907};
  123.         int euler = phi(MOD);
  124.         fact[0] = 1;
  125.         invf[0] = 1;
  126.         for(int i = 1; i <= n; i++) num[i] = i;
  127.         for(int i = 0; i < 4; i++) {
  128.             for(int j = 1; j <= n; j++) {
  129.                 cnt[i][j] = cnt[i][j - 1];
  130.                 while(num[j] % prime[i] == 0) {
  131.                     num[j] /= prime[i];
  132.                     cnt[i][j]++;
  133.                 }
  134.             }
  135.         }
  136.  
  137.         for(int i = 1; i <= n; i++) {
  138.             fact[i] = fact[i - 1] * num[i] % MOD;
  139.             invf[i] = Power(fact[i], euler - 1, MOD);
  140.         }
  141.  
  142.         for(int i = k; i <= n; i++) {
  143.             f[i] = fact[i] * invf[k] % MOD * invf[i - k] % MOD;
  144.             for(int j = 0; j < 4; j++) {
  145.                 int b = cnt[j][i] - cnt[j][k] - cnt[j][i - k];
  146.                 f[i] = f[i] * Power(prime[j], b, MOD) % MOD;
  147.             }
  148.         }
  149.     }
  150.  
  151.     dfs(1, 0);
  152.     ll res = 0;
  153.     for(int i = 1; i <= n; i++) add(res, ans[i]);
  154.     cout << res;
  155. }
  156.  
  157. int main()
  158. {
  159.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  160.     #ifndef ONLINE_JUDGE
  161.     freopen("input.txt", "r", stdin);
  162.     freopen("output.txt", "w", stdout);
  163.     #else
  164.     //online
  165.     #endif
  166.  
  167.     int tc = 1, ddd = 0;
  168.     // cin >> tc;
  169.     while(tc--) {
  170.         //ddd++;
  171.         //cout << "Case #" << ddd << ": ";
  172.         solve();
  173.     }
  174. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement