GCD，LCM
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int ngcd(int* a, int n) { //数组指针与数组大小
if (n == 1)
return *a;
return gcd(a[n - 1], ngcd(a, n - 1));
}
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
int nlcm(int* a, int n) {
if (n == 1)
return *a;
else
return lcm(a[n - 1], nlcm(a, n - 1));
}
扩展欧几里得算法
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;
}
应用的时候可以同时求最大公约数和二元一次方程的解；
比如：ax+by=k；
如果这个方程组有解，那么k % gcd(a,b) == 0；假设有解的情况下去解这个方程；
那么先用exgcd解方程 ax + by = gcd(a,b); 设解为x0，y0；
通解形式：
x = x0/gcd(a,b)*k + b/gcd(a,b) * n (相当于 x 每次可以增减：b/gcd 的整数倍)
y = y0/gcd(a,b)*k + a/gcd(a,b) * n (相当于 y 每次可以增减：a/gcd 的整数倍)
《注意：x 求出来后，y 通常由 x 代入方程求得》
求ax ≡ b(mod m) -> ax + my = b 有解条件为gcd(a,m)|b 特别的,当b=1且a与m互质时,所求x即为a的逆元
中国剩余定理
x ≡ a1(mod m1)
x ≡ a2(mod m2)
......
x ≡ an(mod mn)
M = m1 * m2 * ... * mn Mi = M / mi ti 是 Mi 关于mi的逆元,即Mi*ti ≡ 1(mod mi)
解为 x = sum(ai * Mi * ti) i = 1,2...n
/*当模数两两互质时*/
signed main() {
cin >> n;
ll M = 1;
rep(i, 1, n) {
cin >> A[i] >> B[i]; // A[i] -> mi, B[i] -> ai
M *= A[i];
}
ll res = 0;
rep(i, 1, n) {
ll Mi = M / A[i];
ll ti, x;
exgcd(Mi, A[i], ti, x); //求逆元
res += B[i] * Mi * ti;
}
cout << (res % M + M) % M << '\n';
}
/*当模数不满足两两互质时*/
/*考虑数学归纳法，每次将两个式子合并*/
/*
假设已经求出了前k-1个方程的一个解x, 记m = lcm(m1, m2, ..., mk-1), 则x + i*m 是前k - 1个方程的通解
考虑第k个方程, 求出一个整数t, 使得x + t*m ≡ ak(mod mk), 即m*t ≡ ak - x(mod mk), 这是一个线性同余方程, 可以用exgcd
判断是否有解,并求解。若有解, 则x' = x + t*m 就是前k个方程构成的方程组的一个解。以此类推, 用n次exgcd。
*/
ll mod(ll a, ll b) {
return ((a % b) + b) % b;
}
signed main() {
cin >> n;
ll a1, m1;
cin >> a1 >> m1;
rep(i, 1, n - 1) {
ll a2, m2, k1, k2;
cin >> a2 >> m2;
ll d = exgcd(m1, -m2, k1, k2);
if ((a2 - a1) % d) { // 判断无解情况
cout << "-1\n";
return 0;
}
k1 = mod(k1 * (a2 - a1) / d, abs(m2 / d)); // 按比例缩放
a1 = k1 * m1 + a1; // 特解
m1 = abs(m1 / d * m2); // 前k - 1个模数的最小公倍数
}
cout << a1 << endl;
}
试除法判断质数
bool isPrime(int x) {
if(x < 2) return false;
for(int i = 2; i <= x / i; ++i)
if(x % i == 0) return false;
return true;
}
Miller_Rabin判断质数
ll qmi(ll a, ll b, ll mod) {
ll res = 0;
while (b) {
if (b & 1)
res = (res + a) % mod;
a = (a + a) % mod;
b >>= 1;
}
return res;
}
ll pow(ll a, ll n, ll mod) {
ll res = 1;
while (n) {
if (n & 1)
res = qmi(res, a, mod);
a = qmi(a, a, mod);
n >>= 1;
}
return res;
}
// Miller-Rabin随机算法检测n是否为素数
bool Miller_Rabin(ll n) {
if (n == 2)
return true;
if (n < 2 || !(n & 1))
return false;
ll m = n - 1, k = 0;
while (!(m & 1)) {
k++;
m >>= 1;
}
for (int i = 1; i <= 20; i++) { // 20为Miller-Rabin测试的迭代次数
ll a = rand() % (n - 1) + 1;
ll x = pow(a, m, n);
ll y;
for (int j = 1; j <= k; j++) {
y = qmi(x, x, n);
if (y == 1 && x != 1 && x != n - 1)
return false;
x = y;
}
if (y != 1)
return false;
}
return true;
}
分解质因数——试除法
// x中最多只包含一个大于sqrt(x)的质因子
// 所以枚举时,可以先将小于sqrt(x)的质因子枚举出来
// 如果最后x>1,说明这个数就是那个大于sqrt(x)的质因子
void divide(int x) {
for (int i = 2; i <= x/i; i++) {
if (x % i == 0) { //若成立,i一定是质数
int s = 0;
while (x % i == 0)
x /= i, ++s;
cout << i << ' ' << s << endl; //质因数的底数和指数
}
}
if(x > 1) cout << x << ' ' << 1 << endl;
}
/*阶乘分解质因数*/ O(NlogN)
init(n); // 先筛出1~n的质数
for (int i = 0; i < cnt; i++) {
int p = primes[i];
int s = 0;
for (int j = n; j; j /= p) {
s += j / p;
}
cout << p << ' ' << s << endl;
}
筛质数
朴素筛法
bool st[N];
int primes[N], cnt;
void getPrimes(int x) { //O(nlogn)
for (int i = 2; i <= x; i++) {
if (!st[i])
primes[++cnt] = i;
for (int j = i + i; j <= x; j += i)
st[j] = 1;
}
}
埃氏筛法
//只需筛掉质数的倍数
void getPrimes(int x) { // O(n loglogn)
for (int i = 2; i <= x; i++) {
if (!st[i]) {
primes[++cnt] = i;
for (int j = i + i; j <= x; j += i)
st[j] = 1;
}
}
}
线性筛法
// 每个数只被自己的最小质因子筛掉
void getPrimes(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[i * primes[j]] = 1;
if (i % primes[j] == 0)
break;
}
}
}
区间筛
init(50000);
mem(st);
for (int i = 0; i < cnt; i++) {
ll p = primes[i];
ll temp = max((l + p - 1) / p * p, p * 2);
for (ll j = temp; j <= r; j += p)
st[j - l] = 1;
}
cnt = 0;
for (int i = 0; i <= r - l; i++) {
if (!st[i] && i + l >= 2)
primes[cnt++] = i + l;
}
Min_25筛
时间复杂度$O(\frac{n^{0.75}}{logn})$
// 求1~n的质数的和
const int N=1000010;
namespace Min25 {
int prime[N], id1[N], id2[N], flag[N], ncnt, m;
ll g[N], sum[N], a[N], T, n;
inline int ID(ll x) {
return x <= T ? id1[x] : id2[n / x];
}
inline ll calc(ll x) {
return x * (x + 1) / 2 - 1;
}
inline ll f(ll x) {
return x;
}
inline void init() {
ncnt=m=0;
T = sqrt(n + 0.5);
for (int i = 2; i <= T; i++) {
if (!flag[i]) prime[++ncnt] = i, sum[ncnt] = sum[ncnt - 1] + i;
for (int j = 1; j <= ncnt && i * prime[j] <= T; j++) {
flag[i * prime[j]] = 1;
if (i % prime[j] == 0) break;
}
}
for (ll l = 1; l <= n; l = n / (n / l) + 1) {
a[++m] = n / l;
if (a[m] <= T) id1[a[m]] = m; else id2[n / a[m]] = m;
g[m] = calc(a[m]);
}
for (int i = 1; i <= ncnt; i++)
for (int j = 1; j <= m && (ll)prime[i] * prime[i] <= a[j]; j++)
g[j] = g[j] - (ll)prime[i] * (g[ID(a[j] / prime[i])] - sum[i - 1]);
}
inline ll solve(ll x) {
if (x <= 1) return x;
return n = x, init(), g[ID(n)];
}
}
int main()
{
ll n;
cin >> n;
cout << Min25::solve(n) << endl;
}
莫比乌斯函数
// 在线性筛的同时求出
void init(int n) {
mobius[1] = 1;
for (int i = 2; i <= n; i++) {
if (!st[i]) {
primes[cnt++] = i;
mobius[i] = -1;
}
for (int j = 0; primes[j] <= n / i; j++) {
st[i * primes[j]] = 1;
if (i % primes[j] == 0) {
mobius[i * primes[j]] = 0;
break;
}
mobius[i * primes[j]] = -mobius[i];
}
}
}
约数
试除法求约数
vector<int> getDivisors(int x) { //O(sqrt(n))
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;
}
筛质数+DFS求约数
// 先筛出2~sqrt( n ) 的质数,用这些质数去试除n,保存能整除的质数及指数,再DFS求约数
const int N = 45000, M = 50;
pii factor[M]; //不同质因子,及其指数
int fcnt;
int dividor[N], dcnt; //存约数
void dfs(int u, int p) { //根据质因子求约数
if (u == fcnt) {
dividor[dcnt++] = p;
return;
}
for (int i = 0; i <= factor[u].second; i++) {
dfs(u + 1, p);
p *= factor[u].first;
}
}
int temp = n;
for (int i = 0; primes[i] <= temp / primes[i]; i++) {
int p = primes[i];
if (temp % p == 0) {
int s = 0;
while (temp % p == 0) {
temp /= p;
s++;
}
factor[fcnt++] = {p, s};
}
}
if (temp > 1)
factor[fcnt++] = {temp, 1};
dfs(0, 1);
约数个数
// int 范围内约数个数最多1600 2e9范围内最多1536
unordered_map<int, int> primes;
void getRivisorsCnt(int x) {
for (int i = 2; i <= x / i; i++) {
while (x % i == 0) {
x /= i;
primes[i]++;
}
}
if (x > 1)
primes[x]++;
}
ll res = 1;
for (auto prime : primes)
res = res * (prime.second + 1);
约数之和
ll res = 1;
for (auto prime : primes) {
int p = prime.first, c = prime.second;
ll temp = 1;
while (c--)
temp = (temp * p + 1) % mod;
res = res * temp % mod;
}
cout << res << endl;
快速幂
ll qmi(ll a, ll k) {
ll res = 1;
while (k) {
if (k & 1)
res = res * a % mod;
a = a * a % mod;
k >>= 1;
}
return res;
}
龟速乘
ll gmul(ll a, ll k, ll p) {
ll res = 0;
while (k) {
if (k & 1)
res = (res + a) % p;
a = (a + a) % p;
k >>= 1;
}
return res;
}
ll qmi(ll a, ll k, ll p) {
ll res = 1;
while (k) {
if (k & 1)
res = gmul(res, a, p);
a = gmul(a, a, p);
k >>= 1;
}
return res;
}
分治法等比数列求和
$O(logN)$
int sum(int p, int k) { //等比数列求和,最低次为0,最高次为k-1
if (k == 1)
return 1;
if (k % 2 == 0)
return (1 + qmi(p, k / 2)) * sum(p, k / 2) % mod;
else
return (sum(p, k - 1) + qmi(p, k - 1)) % mod;
}
欧拉函数
对于正整数n,欧拉函数是小于或等于n的正整数中与n互质的数的数目，记作φ(n).
小于等于正整数n且与n互质的正整数的和为 n * φ(n) / 2 , 平均值为 n / 2
φ(1)=1
朴素写法
cin >> n;
int res = n;
for (int i = 2; i <= n / i; i++) {
if (n % i == 0) {
res = res / i * (i - 1);
while (n % i == 0)
n /= i;
}
if (n > 1)
res = res / n * (n - 1);
}
cout << res << endl;
筛法求欧拉函数
const int N = 1e6 + 10;
int n;
int primes[N], cnt;
int phi[N];
bool st[N];
ll get_eulers(int n) {
phi[1] = 1;
for (int i = 2; i <= n; i++) {
if (!st[i]) {
primes[cnt++] = i;
phi[i] = i - 1; // 质数的欧拉函数为其值减一
}
for (int j = 0; primes[j] <= n / i; j++) {
st[i * primes[j]] = 1;
if (i % primes[j] == 0) {
phi[i * primes[j]] = phi[i] * primes[j];
break;
}
phi[i * primes[j]] = phi[i] * (primes[j] - 1);
}
}
ll res = 0;
for (int i = 1; i <= n; i++)
res += phi[i];
return res;
}
高斯消元
解线性方程组
const int N = 110;
const double eps = 1e-6;
int n;
double a[N][N];
int gauss() {
int c, r; // c 表示列，r 表示行
//找主元
for (c = 0, r = 0; c < n; ++c) {
int t = r;
for (int i = r +1; i < n; ++i)
if (fabs(a[i][c]) > fabs(a[t][c]))
t = i;
//因为 C++ 中浮点数存的时候是有误差的
//所以判断其是否为 0 的方法是判断其是否小于一个很小的数
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) //该行除以左侧的数，左侧变为1
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; // 0=非零，无解
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; //唯一解
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i)
for (int j = 0; j <= n; ++j)
scanf("%lf", &a[i][j]);
int t = gauss();
// t=0表示有唯一解，t=1说明无穷多组解，t=2说明无解
if (t == 0)
for (int i = 0; i < n; ++i)
printf("%.2lf\n", a[i][n]);
else if (t == 1)
puts("Infinite group solutions");
else
puts("No solution");
}
解异或方程组
const int N = 110;
int n;
int a[N][N];
int gauss() {
int c, r; // c 表示列，r 表示行
for (c = 0, r = 0; c < n; ++c) {
int t = -1;
for (int i = r; i < n; ++i)
if (a[i][c]) {
t = i;
break;
}
if (t == -1)
continue;
if (!a[t][c])
continue;
for (int i = c; i <= n; ++i) //交换两行
swap(a[t][i], a[r][i]);
for (int i = r + 1; i < n; i++)
if (a[i][c])
for (int j = n; j >= c; j--)
a[i][j] ^= a[r][j];
++r;
}
if (r < n) {
for (int i = r; i < n; ++i)
if (a[i][n])
return 2; // 0=非零，无解
return 1; //多组解
}
for (int i = n - 1; i >= 0; --i)
for (int j = i + 1; j < n; ++j)
if (a[i][j]) // 第j列为1,要靠第j行来消
a[i][n] ^= a[j][n];
return 0; //唯一解
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i)
for (int j = 0; j <= n; ++j)
cin >> a[i][j];
int t = gauss();
// t=0表示有唯一解，t=1说明多组解，t=2说明无解
if (t == 0)
for (int i = 0; i < n; ++i)
cout << a[i][n] << '\n';
else if (t == 1)
puts("Multiple sets of solutions");
else
puts("No solution");
}
矩阵乘法
求斐波那契数列前n项和
const int N = 3;
int n, m;
void mul(int c[], int a[], int b[][N]) {
int temp[N] = {0};
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
temp[i] = (temp[i] + (ll)a[j] * b[j][i]) % m;
}
}
memcpy(c, temp, sizeof temp);
}
void mul(int c[][N], int a[][N], int b[][N]) {
int temp[N][N] = {0};
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
for (int k = 0; k < N; k++) {
temp[i][j] = (temp[i][j] + (ll)a[i][k] * b[k][j]) % m;
}
}
}
memcpy(c, temp, sizeof temp);
}
signed main() {
cin >> n >> m;
int f1[N] = {1, 1, 1};
int a[N][N] = {{0, 1, 0}, {1, 1, 1}, {0, 0, 1}};
n--;
while (n) { // 与快速幂结合
if (n & 1)
mul(f1, f1, a); // f1 = f1 * a;
mul(a, a, a); // a = a*a;
n >>= 1;
}
cout << f1[2] << endl;
}
GT考试（HNOI2008）（矩阵乘法+KMP优化DP）
题意：$x_1，x_2，…，x_n$没有恰好一段等于$a_1, a_2, …, a_n$，$a_1和x_1$可以为0。 第一行输入$n, m, K$，接下来一行输入$m$位不吉利数字
输出不出现不吉利的号码有多少种, 结果对$K$取余
$0<=x_i, a_i<=9$
$1<=n<=10^9$
$1<=m<=20$
$2<=K<=1200$
const int N = 25;
int n, m, mod;
char str[N];
int ne[N];
int a[N][N];
void mul(int c[][N], int a[][N], int b[][N]) {
static int t[N][N];
memset(t, 0, sizeof t);
for (int i = 0; i < m; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < m; k++) {
t[i][j] = (t[i][j] + a[i][k] * b[k][j]) % mod;
}
}
}
memcpy(c, t, sizeof t);
}
int qmi(int k) {
int f[N][N] = {1};
while (k) {
if (k & 1)
mul(f, f, a);
mul(a, a, a);
k >>= 1;
}
int res = 0;
for (int i = 0; i < m; i++)
res = (res + f[0][i]) % mod;
return res;
}
int main() {
cin >> n >> m >> mod;
cin >> str + 1;
for (int i = 2, j = 0; i <= m; i++) {
while (j && str[j + 1] != str[i])
j = ne[j];
if (str[j + 1] == str[i])
j++;
ne[i] = j;
}
// 状态表示：长度为i,不包含str串,且末尾与str匹配的最大长度是j
// 看f(i,j)能够构造出哪些f(i+1,k)
for (int j = 0; j < m; j++) { //不能完全匹配,长度要小于m
for (int c = '0'; c <= '9'; c++) { //枚举下一位
int k = j;
while (k && str[k + 1] != c)
k = ne[k];
if (str[k + 1] == c)
k++;
if (k < m)
a[j][k]++;
}
}
// 可以发现矩阵A只与str串有关,则A不变
// 凡是动态规划中两层之间的转移形式是乘以一个固定矩阵的，都可以使用快速幂优化。
// F(n) = F(0) * A^(n);
cout << qmi(n) << endl;
}
组合数
递推法求组合数(数据规模很小)
***1 <= n <= 1e4 1<=b<=a<=2000 递推 ****
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;
}
}
}
通过预处理逆元的方式求组合数（数据规模上万）
*** 1<=n<=1e4 1<=b<=a<=1e5 预处理阶乘 利用逆元***
const int N = 1e5 + 10, 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;
}
void init() { //初始化阶乘及阶乘的逆元
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;
}
}
signed main() {
int n;
cin >> n;
init();
while (n--) {
int a, b;
cin >> a >> b;
cout << (ll)fact[a] * infact[b] % mod * infact[a - b] % mod << '\n';
}
}
Lucas定理（数据规模上亿）
***1<=n<=20 1<=b<=a<=1e18 1<=p<=1e5 Lucas定理
若p是质数，则对于任意整数 1 <= m <= n，有：
C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)
int 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) {
int res = 1;
// 这里直接用组合数的定义,即分子为a到a-b+1,分母为1到b这几项
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;
}
signed main() {
jiasu;
int n;
cin >> n;
while (n--) {
ll a, b;
cin >> a >> b >> p;
cout << lucas(a, b) << '\n';
}
}
分解质因数法+高精度求组合数（不取模）
***1<=b<=a<=5000 （不取模）用高精度计算 ***
/*先求出分子分解质因数后的指数,再减去分母分解质因数后的指数即可*/
const int N = 10010;
int primes[N], cnt;
bool st[N];
int a[N], b[N];
void init(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[i * primes[j]] = 1;
if (i % primes[j] == 0)
break;
}
}
}
int get(int n, int p) { // 得到n的阶乘中p的指数
int s = 0;
while (n) {
s += n / p;
n /= p;
}
return s;
}
void mul(int r[], int x) {
int t = 0;
for (int i = 1; i <= r[0]; i++) {
r[i] = r[i] * x + t;
t = r[i] / 10;
r[i] %= 10;
}
while (t) {
r[++r[0]] = t % 10;
t /= 10;
}
}
void sub(int a[], int b[]) {
int c[N] = {0};
c[0] = a[0];
for (int i = 1; i <= a[0]; i++) {
if (a[i] >= b[i])
c[i] = a[i] - b[i];
else {
c[i] = a[i] + 10 - b[i];
a[i + 1]--;
}
}
while (c[c[0]] == 0 && c[0] > 1)
c[0]--;
memcpy(a, c, sizeof c);
}
void C(int x, int y, int r[N]) {
r[0] = 1, r[1] = 1;
for (int i = 0; i < cnt; i++) {
int p = primes[i];
int s = get(x, p) - get(y, p) - get(x - y, p);
while (s--)
mul(r, p);
}
}
signed main() {
jiasu;
init(N - 1);
int n, m;
cin >> n >> m;
C(n + m, n, a);
C(n + m, m - 1, b);
sub(a, b); // a – b 存入a
for (int i = a[0]; i >= 1; i--) {
cout << a[i];
}
}
康托展开
康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。
const int MAX = 13;
int Fac[MAX], N;
//求出阶乘
void init() {
Fac[0] = 1;
for (int i = 1; i <= N; ++i) {
Fac[i] = Fac[i - 1] * i;
}
}
int Cantor(int* x) {
int res = 0;
for (int i = 1; i <= N; ++i) {
int Count = 0;
for (int j = i + 1; j <= N; ++j) {
if (x[j] < x[i])
Count++;
}
res += Fac[N - i] * Count;
}
return res;
}
void DeCantor(int pos, int* x) {
set<int> st;
for (int i = 1; i <= N; ++i) {
st.insert(i);
}
for (int i = 1; i <= N; ++i) {
int r = pos / Fac[N - i];
pos %= Fac[N - i];
set<int>::iterator it;
int Count = 0;
for (it = st.begin(); it != st.end(); ++it) {
Count++;
if (Count == r + 1) {
break;
}
}
x[i] = *it;
st.erase(it);
}
}
int main(void) {
int x[MAX], pos;
cin >> N;
init();
cin >> pos;
DeCantor(pos, x);
cout << "DeCantor:" << endl;
for (int i = 1; i <= N; ++i) {
cout << x[i] << " ";
}
cout << endl;
cout << "Cantor:" << endl;
cout << Cantor(x) << endl;
return 0;
}
卡特兰数
卡特兰数的应用都可以归结到一种情况：有两种操作，分别为操作一和操作二，它们的操作次数相同，都为 N，且在进行第 K 次操作二前必须先进行至少 $K $次操作一，问有多少中情况？结果就$Catalan(N)$。
$C_n = C_{2n}^{n} - C_{2n}^{n-1} = \frac{C_{2n}^{n}}{n+1}$
$C_n = C_0 \times C_{n-1} + C_1 \times C_{n-2} + ...... + C_{n-1} \times C_0$[HTML_REMOVED][HTML_REMOVED][HTML_REMOVED][HTML_REMOVED][HTML_REMOVED][HTML_REMOVED][HTML_REMOVED][HTML_REMOVED][HTML_REMOVED][HTML_REMOVED][HTML_REMOVED][HTML_REMOVED]$C_0 = 1$
$C_n = \frac{C_{n-1} \times (4 \times n - 2)}{n+1}$
典型应用:
1.由n个+1和n个-1组成的排列中，满足前缀和>=0的排列有Catalan(N)种。
2.括号化问题。左括号和右括号各有n个时，合法的括号表达式的个数有Catalan(N)种。
3.有n+1个数连乘，乘法顺序有Catalan(N)种,相当于在式子上加括号。
4.n个数按照特定顺序入栈，出栈顺序随意，可以形成的排列的种类有Catalan(N)种。
5.给定N个节点，能构成Catalan(N)种种形状不同的二叉树。
6.n个非叶节点的满二叉树的形态数为Catalan(N)。
7.对于一个n*n的正方形网格，每次只能向右或者向上移动一格，不能穿越对角线，那么从左下角到右上角的不同种类有Catalan(N)种。
8.对于在n位的2进制中，有m个0，其余为1的catalan数为：C（n,m）-C(n,m-1)。
9.对凸n+2边形进行不同的三角形分割（只连接顶点对形成n个三角形）数为Catalan(N)。
10.将有2n个元素的集合中的元素两两分为n个子集，若任意两个子集都不交叉，那么我们称此划分为一个不交叉划分。此时不交叉的划分数是Catalan(N)。
11.n层的阶梯切割为n个矩形的切法数也是Catalan(N)。
12.在一个2*n的格子中填入1到2n这些数值使得每个格子内的数值都比其右边和上边的所有数值都小的情况数也是Catalan(N)。
前30项卡特兰数:
[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, 18367353072152, 69533550916004, 263747951750360, 1002242216651368, 3814986502092304]
博弈论
巴什博奕
一堆石子每次拿1~m个， 若石子总数是$m+1$的整数倍，先手必败，反之先手必胜
对称博弈（摆一排，可以连续拿）
$m=1 $时 ，奇数，先手必胜 偶数，先手必败
$m!=1$时 ，先手必胜 先手可以把物品分成对称的两份
斐波那契博弈
第一个人至少取一个，最多随便取，但是第一回合不能取完，之后每个人取得数目至少为1，
至多为上一个人的2倍，不能取的人输
当n为斐波那契数列中的某个数时，先手必败，反之先手必胜
威佐夫博弈
两堆石子，每个人可以从一堆取任意个石子或者从两堆取任意相同数目的石子
设两堆为a,b,且a>=b, s为黄金分割数 (sqrt(5) + 1) / 2，则 b = floor ( s*(a-b) ) 时，后手必胜，反之先手必胜
NIM博弈
若子游戏可任意取，则其sg值是数量x
sg定理：一个游戏的sg值是它所有子游戏的sg函数异或值
sg值为0，后手必胜，sg值不为0，先手必胜
vector<int> sg(maxn, -1);
int SG(int x){
//记忆化搜索，不为-1就返回
if(~sg[x]) return sg[x];
//一个点的sg值为其所有后继状态的mex
map<int, bool> has;//记录后继状态求mex
for(int i = 1; i <= x; ++i){
int val = SG(x-i);
has[val] = true;
}
for(int i = 0; ; ++i){
if(!has.count(i)){
return sg[x] = i;
}
}
}
树上删边游戏
对于一棵有根树，每次删除现有的一条边，并移除与跟不连通的连通块，不能操作者输掉游戏
结论：
叶子节点的sg值为0
非叶子结点的sg值为它所有儿子节点的sg值+1 的异或和
图上删边
奇环等效于一条边+一个点，偶环等效于一个点，之后就可以按照树上删边来写
阶梯博弈
在1到n的阶梯上，每层有若干本书，每次可以将任意一个阶梯的任意本书向下移动一层，第一层移动到0层，不能移动的人输
结论：
等效于奇数层阶梯上书本数目的nim博弈，sg(1),sg(3)......
为什么？
移动偶数层采用对称的思想，可使奇数层不变，是无效的，而移动奇数层，就相当于拿石子
anti博弈
反nim博弈？不能操作的人赢
求sg值过程不变
必胜态：sg不为0且至少有一堆石子数目大于1 或 sg为0且所有堆石子数目都小于1
有向图博弈
从2出发，先走到1的赢
dp[i][j]，为第i个人，处在j位置上的状态，0平局，1为胜，2为负，显然1为必败点，将其放入队列用逆拓扑排序的思想来bfs更新状态
当前点为必败点，则其前驱状态都为必胜点；当前为必胜点，则记录一下它的前驱状态，如果某个前驱状态所有后继都是比胜点，则这个点也为必败点；最终未被标记的点为平局。
