# dsu and ncr

Apr 19th, 2021
439
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. struct DSU {
2.   struct Node {
3.     int p, sz;
4.   };
5.   vector<Node> dsu;
6.   int cc;
7.
8.   Node &operator[](int id) { return dsu[root(id)]; }
9.
10.   DSU(int n) {
11.     dsu = vector<Node>(n);
12.     for (int i = 0; i < n; i++) {
13.       cc = n;
14.       dsu[i].p = i;
15.       dsu[i].sz = 1;
16.     }
17.   }
18.   //gives the parent or root of the node
19.   inline int root(int u) { return (dsu[u].p == u) ? u : dsu[u].p = root(dsu[u].p); }
20.
21.   inline bool sameSet(int u, int v) { return root(u) == root(v); }
22.
23.   void merge(int u, int v) {
24.     u = root(u);
25.     v = root(v);
26.     if (u == v) return;
27.     if (dsu[u].sz < dsu[v].sz) swap(u, v);
28.     dsu[v].p = u;
29.     dsu[u].sz += dsu[v].sz;
30.     cc--;
31.   }
32.   // size of the set where the node belongs
33.   inline int get_set_size(int u) { return dsu[root(u)].sz; }
34. };
35.
36.
37. struct BinomialCoefficient {
38.   int MAX_N = 1e6 + 1;
39.   const int MOD = 1e9 + 7;
40.
41.   long long power(long long a, long long b, long long m) {
42.     long long res = 1;
43.     while (b) {
44.       if (b & 1) res = res * a % m;
45.       a = a * a % m;
46.       b >>= 1;
47.     }
48.     return res;
49.   }
50.
51.   vector<long long> fact, inv;
52.   vector<double> log_fact;
53.
54.   BinomialCoefficient() {
55.     fact.resize(MAX_N);
56.     inv.resize(MAX_N);
57.     log_fact.resize(MAX_N);
58.   }
59.
60.   void precompute() {
61.     fact[0] = inv[0] = 1;
62.     for (int i = 1; i < MAX_N; i++) {
63.       fact[i] = fact[i - 1] * i % MOD;
64.       inv[i] = power(fact[i], MOD - 2, MOD); // Fermat's little theorem
65.     }
66.   }
67.
68.   long long nCk(int n, int k) {
69.     if (k < 0 || k > n) return 0;
70.     return fact[n] * inv[k] % MOD * inv[n - k] % MOD;
71.
72.     // if there are only a few queries, then don't need to precompute inv[] => faster
73.     // return fact[n] * power(fact[k], MOD - 2, MOD) % MOD * power(fact[n - k], MOD - 2, MOD) % MOD;
74.   }
75.
76. // A trick to calculate large factorial without overflowing is to take log at every step when precompute and take exponential when calculating
77. // Don't need inv[] now because it is the same as negative log of fact
78.   void precompute_log() {
79.     log_fact[0] = 0.0;
80.     for (int i = 1; i < MAX_N; i++)
81.       log_fact[i] = log_fact[i - 1] + log(i);
82.   }
83.
84.   long long log_nCk(int n, int k) {
85.     if (k < 0 || k > n) return 0;
86.     return exp(log_fact[n] - log_fact[n - k] - log_fact[k]);
87.   }
88. };
RAW Paste Data

# Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×