4.4 快速幂
快速幂 —— 模板题 AcWing 875. 快速幂
求 m^k mod p，时间复杂度 O(logk)。
int qmi(int m, int k, int p) { int res = 1 % p, t = m; while (k) { if (k&1) res = res * t % p; t = t * t % p; k >>= 1; } return res; }
4.4.1 875. 快速幂
给定 n 组 ai,bi,pi，对于每组数据，求出 abiimodpi 的值。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含三个整数 ai,bi,pi。
输出格式
对于每组数据，输出一个结果，表示 abiimodpi 的值。
每个结果占一行。
数据范围
1≤n≤100000,
1≤ai,bi,pi≤2×109
输入样例：
2
3 2 5
4 3 9
输出样例：
4
1
#include<bits/stdc++.h> using namespace std; typedef long long LL; LL qmi(int a,int k,int p) { LL res=1; while(k) { if(k&1) res=(LL)res*a%p; k>>=1; a=(LL)a*a%p; } return res; } int main() { int n; cin>>n; while(n--) { int a,k,p; cin>>a>>k>>p; cout<<qmi(a,k,p)<<endl; } return 0; }
4.4.2 876. 快速幂求逆元
给定 n 组 ai,pi，其中 pi 是质数，求 ai 模 pi 的乘法逆元，若逆元不存在则输出 impossible。
注意：请返回在 0∼p−1 之间的逆元。
乘法逆元的定义
若整数 b，m 互质，并且对于任意的整数 a，如果满足 b|a，则存在一个整数 x，使得 a/b≡a×x(modm)，则称 x 为 b 的模 m 乘法逆元，记为 b−1(modm)。
b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时，bm−2 即为 b 的乘法逆元。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一个数组 ai,pi，数据保证 pi 是质数。
输出格式
输出共 n 行，每组数据输出一个结果，每个结果占一行。
若 ai 模 pi 的乘法逆元存在，则输出一个整数，表示逆元，否则输出 impossible。
数据范围
1≤n≤105,
1≤ai,pi≤2∗109
输入样例：
3
4 3
8 5
6 3
输出样例：
1
2
Impossible
#include<bits/stdc++.h> using namespace std; typedef long long LL; LL qmi(int a,int k,int p) { LL res=1; while(k) { if(k&1) res=(LL)res*a%p; k>>=1; a=(LL)a*a%p; } return res; } int main() { int n; cin>>n; while(n--) { int a,p; cin>>a>>p; LL res=qmi(a,p-2,p); if(a%p) cout<<res<<endl; else cout<<"impossible"<<endl; } return 0; }
4.5 扩展欧几里得算法
扩展欧几里得算法 —— 模板题 AcWing 877. 扩展欧几里得算法
// 求x, y，使得ax + by = gcd(a, b) int exgcd(int a, int b, int &x, int &y) { if (!b) { x = 1; y = 0; return a; } int d = exgcd(b, a % b, y, x); y -= (a/b) * x; return d; }
4.5.1 877. 扩展欧几里得算法
给定 n 对正整数 ai,bi，对于每对数，求出一组 xi,yi，使其满足 ai×xi+bi×yi=gcd(ai,bi)。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含两个整数 ai,bi。
输出格式
输出共 n 行，对于每组 ai,bi，求出一组满足条件的 xi,yi，每组结果占一行。
本题答案不唯一，输出任意满足条件的 xi,yi 均可。
数据范围
1≤n≤105,
1≤ai,bi≤2×109
输入样例：
2
4 6
8 18
输出样例：
-1 1
-2 1
#include<bits/stdc++.h> using namespace std; int exgcd(int a,int b,int &x,int &y) { if(!b) { x=1,y=0; return a; } int d=exgcd(b,a%b,y,x); y-=a/b*x; return d; } int main() { int n; cin>>n; while(n--) { int a,b,x,y; cin>>a>>b; exgcd(a,b,x,y); cout<<x<<" "<<y<<endl; } return 0; }
4.5.2 878. 线性同余方程
给定 n 组数据 ai,bi,mi，对于每组数求出一个 xi，使其满足 ai×xi≡bi(modmi)，如果无解则输出 impossible。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一组数据 ai,bi,mi。
输出格式
输出共 n 行，每组数据输出一个整数表示一个满足条件的 xi，如果无解则输出 impossible。
每组数据结果占一行，结果可能不唯一，输出任意一个满足条件的结果均可。
输出答案必须在 int 范围之内。
数据范围
1≤n≤105,
1≤ai,bi,mi≤2×109
输入样例：
2
2 3 6
4 3 5
输出样例：
impossible
-3
#include<bits/stdc++.h> using namespace std; typedef long long LL; int exgcd(int a,int b,int &x,int &y) { if(!b) { x=1,y=0; return a; } int d=exgcd(b,a%b,y,x); y-=a/b*x; return d; } int main() { int n; cin>>n; while(n--) { int a,b,m,x,y; cin>>a>>b>>m; int d=exgcd(a,m,x,y); if(b%d) cout<<"impossible"<<endl; else cout<<(LL)x*(b/d)%m<<endl; } return 0; }
4.6 中国剩余定理
4.6.1 204. 表达整数的奇怪方式
给定 2n 个整数 a1,a2,…,an 和 m1,m2,…,mn，求一个最小的非负整数 x，满足 ∀i∈[1,n],x≡mi(mod ai)。
输入格式
第 1 行包含整数 n。
第 2…n+1 行：每 i+1 行包含两个整数 ai 和 mi，数之间用空格隔开。
输出格式
输出最小非负整数 x，如果 x 不存在，则输出 −1。
如果存在 x，则数据保证 x 一定在 64 位整数范围内。
数据范围
1≤ai≤231−1,
0≤mi<ai
1≤n≤25
输入样例：
2
8 7
11 9
输出样例：
31
#include<bits/stdc++.h> using namespace std; typedef long long LL; LL exgcd(LL a,LL b,LL &x,LL &y) { if(!b) { x=1,y=0; return a; } LL d=exgcd(b,a%b,y,x); y-=a/b*x; return d; } int main() { int n; cin>>n; bool flag=true; LL a1,m1; cin>>a1>>m1; for(int i=0;i<n-1;i++) { LL a2,m2; cin>>a2>>m2; LL k1,k2; LL d=exgcd(a1,a2,k1,k2); if((m2-m1)%d) { flag=false; break; } k1*=(m2-m1)/d; LL t=a2/d; k1=(k1%t+t)%t; m1=a1*k1+m1; a1=abs(a1/d*a2); } if(flag) cout<<(m1%a1+a1)%a1<<endl; else cout<<-1<<endl; return 0; }
4.7 高斯消元
高斯消元 —— 模板题 AcWing 883. 高斯消元解线性方程组
// a[N][N]是增广矩阵 int gauss() { int c, r; for (c = 0, r = 0; c < n; c ++ ) { int t = r; for (int i = r; i < n; i ++ ) // 找到绝对值最大的行 if (fabs(a[i][c]) > fabs(a[t][c])) t = i; if (fabs(a[t][c]) < eps) continue; for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]); // 将绝对值最大的行换到最顶端 for (int i = n; i >= c; i -- ) a[r][i] /= a[r][c]; // 将当前行的首位变成1 for (int i = r + 1; i < n; i ++ ) // 用当前行将下面所有的列消成0 if (fabs(a[i][c]) > eps) for (int j = n; j >= c; j -- ) a[i][j] -= a[r][j] * a[i][c]; r ++ ; } if (r < n) { for (int i = r; i < n; i ++ ) if (fabs(a[i][n]) > eps) return 2; // 无解 return 1; // 有无穷多组解 } for (int i = n - 1; i >= 0; i -- ) for (int j = i + 1; j < n; j ++ ) a[i][n] -= a[i][j] * a[j][n]; return 0; // 有唯一解 }
4.7.1 883. 高斯消元解线性方程组
输入一个包含 n 个方程 n 个未知数的线性方程组。
方程组中的系数为实数。
求解这个方程组。
下图为一个包含 m 个方程 n 个未知数的线性方程组示例：
输入格式
第一行包含整数 n。
接下来 n 行，每行包含 n+1 个实数，表示一个方程的 n 个系数以及等号右侧的常数。
输出格式
如果给定线性方程组存在唯一解，则输出共 n 行，其中第 i 行输出第 i 个未知数的解，结果保留两位小数。
如果给定线性方程组存在无数解，则输出 Infinite group solutions。
如果给定线性方程组无解，则输出 No solution。
数据范围
1≤n≤100,
所有输入系数以及常数均保留两位小数，绝对值均不超过 100。
输入样例：
3
1.00 2.00 -1.00 -6.00
2.00 1.00 -3.00 -9.00
-1.00 -1.00 2.00 7.00
输出样例：
1.00
-2.00
3.00
#include<bits/stdc++.h> using namespace std; const int N=110; const double eps=1e-6; int n; double a[N][N]; int gauss() { int c,r; for(c=0,r=0;c<n;c++) { int t=r; for(int i=r;i<n;i++) if(fabs(a[i][c])>fabs(a[t][c])) t=i; if(fabs(a[t][c])<eps) continue; for(int i=c;i<n+1;i++) swap(a[t][i],a[r][i]); for(int i=n;i>=c;i--) a[r][i]/=a[r][c]; for(int i=r+1;i<n;i++) if(fabs(a[i][c])>eps) for(int j=n;j>=c;j--) a[i][j]-=a[r][j]*a[i][c]; r++; } if(r<n) { for(int i=r;i<n;i++) if(fabs(a[i][n])>eps) return 2; return 1; } for(int i=n-1;i>=0;i--) for(int j=i+1;j<n;j++) a[i][n]-=a[j][n]*a[i][j]; return 0; } int main() { cin>>n; for(int i=0;i<n;i++) { for(int j=0;j<n+1;j++) cin>>a[i][j]; } int t=gauss(); if(t==0) { for(int i=0;i<n;i++) printf("%.2f\n",a[i][n]); } else if(t==1) cout<<"Infinite group solutions"<<endl; else cout<<"No solution"<<endl; return 0; }
4.7.2 884. 高斯消元解异或线性方程组
输入一个包含 n 个方程 n 个未知数的异或线性方程组。
方程组中的系数和常数为 0 或 1，每个未知数的取值也为 0 或 1。
求解这个方程组。
异或线性方程组示例如下：
M[1][1]x[1] ^ M[1][2]x[2] ^ … ^ M[1][n]x[n] = B[1]
M[2][1]x[1] ^ M[2][2]x[2] ^ … ^ M[2][n]x[n] = B[2]
…
M[n][1]x[1] ^ M[n][2]x[2] ^ … ^ M[n][n]x[n] = B[n]
其中 ^ 表示异或(XOR)，M[i][j] 表示第 i 个式子中 x[j] 的系数，B[i] 是第 i 个方程右端的常数，取值均为 0 或 1。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含 n+1 个整数 0 或 1，表示一个方程的 n 个系数以及等号右侧的常数。
输出格式
如果给定线性方程组存在唯一解，则输出共 n 行，其中第 i 行输出第 i 个未知数的解。
如果给定线性方程组存在多组解，则输出 Multiple sets of solutions。
如果给定线性方程组无解，则输出 No solution。
数据范围
1≤n≤100
输入样例：
3
1 1 0 1
0 1 1 0
1 0 0 1
输出样例：
1
0
0
#include<bits/stdc++.h> using namespace std; const int N=110; int n; int a[N][N]; int gauss() { int r,c; for(c=0,r=0;c<n;c++) { int t=r; for(int i=r;i<n;i++) if(a[i][c]) { t=i; break; } if(!a[t][c]) continue; for(int i=c;i<n+1;i++) swap(a[t][i],a[r][i]); for(int i=r+1;i<n;i++) if(a[i][c]) for(int j=c;j<=n;j++) a[i][j]^=a[r][j]; r++; } if(r<n) { for(int i=r;i<n;i++) if(a[i][n]) return 2; return 1; } for(int i=n-1;i>=0;i--) for(int j=i+1;j<n;j++) a[i][n]^=a[j][n]&a[i][j]; return 0; } int main() { cin>>n; for(int i=0;i<n;i++) { for(int j=0;j<n+1;j++) cin>>a[i][j]; } int t=gauss(); if(t==0) { for(int i=0;i<n;i++) cout<<a[i][n]<<endl; } else if(t==1) cout<<"Multiple sets of solutions"<<endl; else cout<<"No solution"<<endl; return 0; }
4.8 求组合数
递归法求组合数 —— 模板题 AcWing 885. 求组合数 I
// c[a][b] 表示从a个苹果中选b个的方案数 for (int i = 0; i < N; i ++ ) for (int j = 0; j <= i; j ++ ) if (!j) c[i][j] = 1; else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
通过预处理逆元的方式求组合数 —— 模板题 AcWing 886. 求组合数 II
首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]
如果取模的数是质数，可以用费马小定理求逆元
int qmi(int a, int k, int p) // 快速幂模板 { int res = 1; while (k) { if (k & 1) res = (LL)res * a % p; a = (LL)a * a % p; k >>= 1; } return res; } // 预处理阶乘的余数和阶乘逆元的余数 fact[0] = infact[0] = 1; for (int i = 1; i < N; i ++ ) { fact[i] = (LL)fact[i - 1] * i % mod; infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod; }
Lucas定理 —— 模板题 AcWing 887. 求组合数 III
若p是质数，则对于任意整数 1 <= m <= n，有：
C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)
int qmi(int a, int k, int p) // 快速幂模板 { int res = 1 % p; while (k) { if (k & 1) res = (LL)res * a % p; a = (LL)a * a % p; k >>= 1; } return res; } int C(int a, int b, int p) // 通过定理求组合数C(a, b) { if (a < b) return 0; LL x = 1, y = 1; // x是分子，y是分母 for (int i = a, j = 1; j <= b; i --, j ++ ) { x = (LL)x * i % p; y = (LL) y * j % p; } return x * (LL)qmi(y, p - 2, p) % p; } int lucas(LL a, LL b, int p) { if (a < p && b < p) return C(a, b, p); return (LL)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p; }
分解质因数法求组合数 —— 模板题 AcWing 888. 求组合数 IV
当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用：
1. 筛法求出范围内的所有质数
2. 通过 C(a, b) = a! / b! / (a - b)! 这个公式求出每个质因子的次数。 n! 中p的次数是 n / p + n / p^2 + n / p^3 + …
3. 用高精度乘法将所有质因子相乘
int primes[N], cnt; // 存储所有质数
int sum[N]; // 存储每个质数的次数
bool st[N]; // 存储每个数是否已被筛掉
void get_primes(int n) // 线性筛法求素数 { for (int i = 2; i <= n; i ++ ) { if (!st[i]) primes[cnt ++ ] = i; for (int j = 0; primes[j] <= n / i; j ++ ) { st[primes[j] * i] = true; if (i % primes[j] == 0) break; } } } int get(int n, int p) // 求n！中的次数 { int res = 0; while (n) { res += n / p; n /= p; } return res; } vector<int> mul(vector<int> a, int b) // 高精度乘低精度模板 { vector<int> c; int t = 0; for (int i = 0; i < a.size(); i ++ ) { t += a[i] * b; c.push_back(t % 10); t /= 10; } while (t) { c.push_back(t % 10); t /= 10; } return c; } get_primes(a); // 预处理范围内的所有质数 for (int i = 0; i < cnt; i ++ ) // 求每个质因数的次数 { int p = primes[i]; sum[i] = get(a, p) - get(b, p) - get(a - b, p); } vector<int> res; res.push_back(1); for (int i = 0; i < cnt; i ++ ) // 用高精度乘法将所有质因子相乘 for (int j = 0; j < sum[i]; j ++ ) res = mul(res, primes[i]);
卡特兰数 —— 模板题 AcWing 889. 满足条件的01序列
给定n个0和n个1，它们按照某种顺序排成长度为2n的序列，满足任意前缀中0的个数都不少于1的个数的序列的数量为： Cat(n) = C(2n, n) / (n + 1)
4.8.1 885. 求组合数 I
给定 n 组询问，每组询问给定两个整数 a，b，请你输出 Cbamod(109+7) 的值。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一组 a 和 b。
输出格式
共 n 行，每行输出一个询问的解。
数据范围
1≤n≤10000,
1≤b≤a≤2000
输入样例：
3
3 1
5 3
2 2
输出样例：
3
10
1
#include<bits/stdc++.h> using namespace std; const int N=2010,mod=1e9+7; int c[N][N]; void init() { for(int i=0;i<N;i++) for(int j=0;j<=i;j++) if(!j) c[i][j]=1; else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod; } int main() { init(); int n; cin>>n; while(n--) { int a,b; cin>>a>>b; cout<<c[a][b]<<endl; } return 0; }
4.8.2 886. 求组合数 II
给定 n 组询问，每组询问给定两个整数 a，b，请你输出 Cbamod(109+7) 的值。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一组 a 和 b。
输出格式
共 n 行，每行输出一个询问的解。
数据范围
1≤n≤10000,
1≤b≤a≤105
输入样例：
3
3 1
5 3
2 2
输出样例：
3
10
1
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=100010,mod=1e9+7; int fact[N],infact[N]; int qmi(int a,int k,int p) { int res=1; while(k) { if(k&1) res=(LL)res*a%p; a=(LL)a*a%p; k>>=1; } return res; } int main() { fact[0]=infact[0]=1; for(int i=1;i<N;i++) { fact[i]=(LL)fact[i-1]*i%mod; infact[i]=(LL)infact[i-1]*qmi(i,mod-2,mod)%mod; } int n; cin>>n; while(n--) { int a,b; cin>>a>>b; cout<<(LL)fact[a]*infact[b]%mod*infact[a-b]%mod<<endl; } return 0; }
4.8.3 887. 求组合数 III
给定 n 组询问，每组询问给定三个整数 a,b,p，其中 p 是质数，请你输出 Cbamodp 的值。
输入格式
第一行包含整数 n。
接下来 n 行，每行包含一组 a,b,p。
输出格式
共 n 行，每行输出一个询问的解。
数据范围
1≤n≤20,
1≤b≤a≤1018,
1≤p≤105,
输入样例：
3
5 3 7
3 1 5
6 4 13
输出样例：
3
3
2
#include<bits/stdc++.h> using namespace std; typedef long long LL; int p; int qmi(LL a,int k) { int res=1; while(k) { if(k&1) res=(LL)res*a%p; a=(LL)a*a%p; k>>=1; } return res; } int C(LL a,LL b) { int res=1; for(int i=1,j=a;i<=b;i++,j--) { res=(LL)res*j%p; res=(LL)res*qmi(i,p-2)%p; } return res; } int lucas(LL a,LL b) { if(a<p&&b<p) return C(a,b); return (LL)C(a%p,b%p)*lucas(a/p,b/p)%p; } int main() { int n; cin>>n; while(n--) { LL a,b; cin>>a>>b>>p; cout<<lucas(a,b)<<endl; } return 0; }
4.8.4 888. 求组合数 IV
输入 a,b，求 Cba 的值。
注意结果可能很大，需要使用高精度计算。
输入格式
共一行，包含两个整数 a 和 b。
输出格式
共一行，输出 Cba 的值。
数据范围
1≤b≤a≤5000
输入样例：
5 3
输出样例：
10
#include<bits/stdc++.h> using namespace std; const int N=5010; int primes[N],cnt; int sum[N]; bool st[N]; void get_primes(int n) { for(int i=2;i<=n;i++) { if(!st[i]) primes[cnt++]=i; for(int j=0;primes[j]<=n/i;j++) { st[primes[j]*i]=true; if(i%primes[j]==0) break; } } } int get(int n,int p) { int res=0; while(n) { res+=n/p; n/=p; } return res; } vector<int> mul(vector<int> a,int b) { vector<int> c; int t=0; for(int i=0;i<a.size();i++) { t+=a[i]*b; c.push_back(t%10); t/=10; } while(t) { c.push_back(t%10); t/=10; } return c; } int main() { int a,b; cin>>a>>b; get_primes(a); for(int i=0;i<cnt;i++) { int p=primes[i]; sum[i]=get(a,p)-get(b,p)-get(a-b,p); } vector<int> res; res.push_back(1); for(int i=0;i<cnt;i++) for(int j=0;j<sum[i];j++) res=mul(res,primes[i]); for(int i=res.size()-1;i>=0;i--) cout<<res[i]; return 0; }
4.8.5 889. 满足条件的01序列
给定 n 个 0 和 n 个 1，它们将按照某种顺序排成长度为 2n 的序列，求它们能排列成的所有序列中，能够满足任意前缀序列中 0 的个数都不少于 1 的个数的序列有多少个。
输出的答案对 109+7 取模。
输入格式
共一行，包含整数 n。
输出格式
共一行，包含一个整数，表示答案。
数据范围
1≤n≤105
输入样例：
3
输出样例：
5
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int mod=1e9+7; int qmi(int a,int k,int p) { int res=1; while(k) { if(k&1) res=(LL)res*a%p; a=(LL)a*a%p; k>>=1; } return res; } int main() { int n; cin>>n; int a=2*n,b=n; int res=1; for(int i=a;i>a-b;i--) res=(LL)res*i%mod; for(int i=1;i<=b;i++) res=(LL)res*qmi(i,mod-2,mod)%mod; res=(LL)res*qmi(n+1,mod-2,mod)%mod; cout<<res<<endl; return 0; }
