class Solution {
public:
void nextPermutation(vector<int>& nums) {
int k = nums.size() - 1;
// 1. 找到第一个递减点 e,g, 1,2,3 -> 1,3,2
while(k > 0 && nums[k - 1] >= nums[k]) k--;
if(k == 0) reverse(nums.begin(), nums.end()); // 如果降序排列 直接反转
else
{
// 2. 找到 k - 1 右边第一个比nums[k - 1]大的元素
//int i = nums.size() - 1;
//while(i > k && nums[i] <= nums[k - 1]) i--;
int l = k, r = nums.size() - 1;
while(l < r)
{
int mid = l + r + 1 >> 1;
if(nums[mid] > nums[k - 1]) l = mid;
else r = mid - 1;
}
swap(nums[k - 1], nums[r]);
// 交换完之后仍然是降序（字典序最大) 转换为升序(字典序最小)
reverse(nums.begin() + k, nums.end());
}
}
};
4. 对称的排列
从1...n的全排列满足
正数第Q个排列和倒数第Q个排列满足 对应元素的和 等于 n + 1
2. 试除法判断质数
bool is_prime(int x)
{
if (x < 2) return false;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
return false;
return true;
}
3. 试除法分解质因数
记住分解质因数这里 最后可能还剩下一个因子哦
void divide(int x)
{
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
int s = 0;
while (x % i == 0) x /= i, s ++ ;
cout << i << ' ' << s << endl;
}
if (x > 1) cout << x << ' ' << 1 << endl; // 注意这里
cout << endl;
}
4. 试除法求所有约数
vector<int> get_divisors(int x)
{
vector<int> res;
for (int i = 1; i <= x / i; i ++ )
if (x % i == 0)
{
res.push_back(i);
if (i != x / i) res.push_back(x / i);
}
sort(res.begin(), res.end());
return res;
}
5. 线性筛求素数
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
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 gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
最小公倍数 LCM = a * b / gcd(a, b)
8. 扩展欧几里得算法 （求 ax + by = gcd(a, b))
// 求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;
}
8.1 裴蜀定理(ax + by = c 有解的条件)
当且仅当 gcd(a, b) 可以整除c
a,b互质的充分必要条件是存在整数x,y使 ax+by=1
9. 快速幂
int qmi(int m, int k, int p)
{
int res = 1, t = m%p;
while (k)
{
if (k&1) res = res * t % p;
t = t * t % p;
k >>= 1;
}
return res;
}
10. 欧拉函数
欧拉函数：1 ~ N 中 与N 互质的个数被称为欧拉函数
欧拉定理：若a 与 n互质， 则 a ^(φ(n)) ≡ 1 (mod n)
费马小定理 如果p为质数 b ^(p - 1) ≡ 1 (mod p)
avatar
1. 求欧拉函数
int phi(int x)
{
int res = x;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
if (x > 1) res = res / x * (x - 1);
return res;
}
2. 筛法求 1 ~ N 的欧拉函数
int primes[N], cnt; // primes[]存储所有素数
int euler[N]; // 存储每个数的欧拉函数
bool st[N]; // st[x]存储x是否被筛掉
void get_eulers(int n)
{
euler[1] = 1;
for (int i = 2; i <= n; i ++ )
{
if (!st[i])
{
primes[cnt ++ ] = i;
euler[i] = i - 1;
}
for (int j = 0; primes[j] <= n / i; j ++ )
{
int t = primes[j] * i;
st[t] = true;
if (i % primes[j] == 0)
{
euler[t] = euler[i] * primes[j];
break;
}
euler[t] = euler[i] * (primes[j] - 1);
}
}
}
11. 高斯消元法解线性方程组
// 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; // 有唯一解
}
首先预处理出所有阶乘取模的余数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;
}
3. Lucas定理求组合数
大数组合数
若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 res = 1;
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) // 通过定理求组合数C(a, 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;
}
