# Java 急救模板
## 快速幂、矩阵快速幂
```java
static long qpow_mod(long x, long p, long mod) {
long res = 1;
long base = x % mod;
while (p > 0) {
if ((p & 1) != 0) {
res = res * base % mod;
}
p >>= 1;
base = base * base % mod;
}
return res;
}
// 矩阵乘法（带模运算）a:n*p, b:p*m, c:n*m
static long[][] matrixMultiply(long[][] a, long[][] b, long mod) {
int n = a.length;
int p = a[0].length;
int m = b[0].length;
long[][] res = new long[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < p; k++) {
res[i][j] = (res[i][j] + (a[i][k] * b[k][j]) % mod) % mod;
}
}
}
return res;
}
// 矩阵快速幂（方阵）
static long[][] matrixQpow(long[][] base, long pow, long mod) {
int n = base.length;
// 初始化单位矩阵
long[][] res = new long[n][n];
for (int i = 0; i < n; i++) res[i][i] = 1;
while (pow > 0) {
if ((pow & 1) == 1) {
res = matrixMultiply(res, base, mod);
}
base = matrixMultiply(base, base, mod);
pow >>= 1;
}
return res;
}
```
## 逆元与排列组合计算
- 组合数/排列数
- P(n, m)是从n递减乘m个
- C(n, m)是从n递减乘m个，再除以m的阶乘
```java
static long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}
static long lcm(long a, long b) {
return a / gcd(a, b) * b;
}
static long inv(long a, long m) {
return qpow_mod(a, m-2, m);
}
static long C(long a, long b, long m) {
if (b > a || b < 0) return 0;
long res = 1;
for (long i = 0; i < b; i++) {
res = res * (a - i) % m;
res = res * inv(i + 1, m) % m;
}
return res;
}
static long P(long a, long b, long m) {
if (b > a) return 0;
long res = 1;
for (long i = 0; i < b; i++) {
res = res * (a - i) % m;
}
return res;
}
```
## 并查集
```java
class UnionFind {
private int[] parent;
public UnionFind(int n) {
parent = new int[n + 1];
for (int i = 1; i <= n; i++) parent[i] = i;
}
public int find(int x) {
int t = x;
while (parent[t] != t) t = parent[t];
while (x != t) {
int p = parent[x];
parent[x] = t;
x = p;
}
return t;
}
public void merge(int a, int b) {
parent[find(b)] = find(a);
}
}
```
## Kruskal
```java
class Kruskal {
static class Edge implements Comparable<Edge> {
int u, v, w;
Edge(int u, int v, int w) {
this.u = u;
this.v = v;
this.w = w;
}
public int compareTo(Edge o) {
return this.w - o.w;
}
}
static List<Edge> kruskal(int n, List<Edge> edges) {
Collections.sort(edges);
UnionFind uf = new UnionFind(n);
List<Edge> tree = new ArrayList<>();
for (Edge e : edges) {
if (uf.find(e.u) != uf.find(e.v)) {
uf.merge(e.u, e.v);
tree.add(e);
if (tree.size() == n-1) break;
}
}
return tree.size() == n-1 ? tree : null;
}
}
```
## 树状数组
```java
class TreeArr {
static int lowbit(int x) {
return x & -x;
}
public int n;
public long[] a;
public TreeArr(int n) {
this.n = n;
a = new long[n + 1]; // 下标从1开始
}
// 单点修改（x从1开始）
void add(int x, long v) {
for (; x <= n; x += lowbit(x))
a[x] += v;
}
// 前缀和查询 [1, x]
long sum(int x) {
long res = 0;
for (; x > 0; x -= lowbit(x))
res += a[x];
return res;
}
// 区间和查询 [l, r]
long sum(int l, int r) {
return sum(r) - sum(l-1);
}
}
```
## KMP
```java
static int[] getFail(String p) {
int next[] = new int[p.length() + 1];
Arrays.fill(next, 0);
for (int i = 1; i < p.length(); i++) {
int j = next[i];
while (j > 0 && p.charAt(i) != p.charAt(j))
j = next[j];
if (p.charAt(i) == p.charAt(j))
next[i + 1] = j + 1;
}
return next;
}
static boolean kmp(String s, String p) {
int[] next = getFail(p);
int j = 0;
for (int i = 0; i < s.length(); i++) {
while (j > 0 && s.charAt(i) != p.charAt(j))
j = next[j];
if (s.charAt(i) == p.charAt(j))
j++;
if (j == p.length())
return true;
}
return false;
}
```