combination, lca, mod division

atcoder-live · atcoder-live · commit 4c1d89e5f59c · 2019-07-08T02:23:17.000+09:00
diff --git a/comb.cpp b/comb.cpp
@@ -0,0 +1,16 @@
+[mint]
+// combination mod prime
+// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
+struct combination {
+  vector<mint> fact, ifact;
+  combination(int n):fact(n+1),ifact(n+1) {
+    fact[0] = 1;
+    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
+    ifact[n] = fact[n].inv();
+    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
+  }
+  mint operator()(int n, int k) {
+    if (k < 0 || k > n) return 0;
+    return fact[n]*ifact[k]*ifact[n-k];
+  }
+};
diff --git a/lca.cpp b/lca.cpp
@@ -0,0 +1,67 @@
+// Lowest Common Ancestor by binary lifting
+// https://youtu.be/8uowVvQ_-Mo?t=4306
+template<typename T> // T: type of cost
+struct lca {
+  int n, root, l;
+  vector<vector<int>> to;
+  vector<vector<T>> co;
+  vector<int> dep;
+  vector<T> costs;
+  vector<vector<int>> par;
+  lca(int n):n(n),to(n),co(n),dep(n),costs(n) {
+    l = 0;
+    while ((1<<l) < n) ++l;
+    par = vector<vector<int>>(n+1,vector<int>(l,n));
+  }
+  void addEdge(int a, int b, T c=0) {
+    to[a].push_back(b); co[a].push_back(c);
+    to[b].push_back(a); co[b].push_back(c);
+  }
+  void dfs(int v, int d=0, T c=0, int p=-1) {
+    if (p != -1) par[v][0] = p;
+    dep[v] = d;
+    costs[v] = c;
+    for (int i = 0; i < to[v].size(); ++i) {
+      int u = to[v][i];
+      if (u == p) continue;
+      dfs(u, d+1, c+co[v][i], v);
+    }
+  }
+
+  void init(int _root=0) {
+    root = _root;
+    dfs(root);
+    for (int i = 0; i < l-1; ++i) {
+      for (int v = 0; v < n; ++v) {
+        par[v][i+1] = par[par[v][i]][i];
+      }
+    }
+  }
+  // LCA
+  int operator()(int a, int b) {
+    if (dep[a] > dep[b]) swap(a,b);
+    int gap = dep[b]-dep[a];
+    for (int i = l-1; i >= 0; --i) {
+      int len = 1<<i;
+      if (gap >= len) {
+        gap -= len;
+        b = par[b][i];
+      }
+    }
+    if (a == b) return a;
+    for (int i = l-1; i >= 0; --i) {
+      int na = par[a][i];
+      int nb = par[b][i];
+      if (na != nb) a = na, b = nb;
+    }
+    return par[a][0];
+  }
+  int length(int a, int b) {
+    int c = lca(a,b);
+    return dep[a]+dep[b]-dep[c]*2;
+  }
+  T dist(int a, int b) {
+    int c = lca(a,b);
+    return costs[a]+costs[b]-costs[c]*2;
+  }
+};
diff --git a/mint.cpp b/mint.cpp
@@ -1,8 +1,10 @@
+// auto mod int
 // https://youtu.be/L8grWxBlIZ4?t=9858
-// https://youtu.be/ERZuLAxZffQ?t=4765
+// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
+// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
 const int mod = 1000000007;
 struct mint {
-  ll x;
+  ll x; // typedef long long ll;
   mint(ll x=0):x(x%mod){}
   mint& operator+=(const mint a) {
     if ((x += a.x) >= mod) x -= mod;
@@ -28,4 +30,23 @@ struct mint {
     mint res(*this);
     return res*=a;
   }
+  mint pow(ll t) const {
+    if (!t) return 1;
+    mint a = pow(t>>1);
+    a *= a;
+    if (t&1) a *= *this;
+    return a;
+  }
+
+  // for prime mod
+  mint inv() const {
+    return pow(mod-2);
+  }
+  mint& operator/=(const mint a) {
+    return (*this) *= a.inv();
+  }
+  mint operator/(const mint a) const {
+    mint res(*this);
+    return res/=a;
+  }
 };
