这里写目录标题

• 基础算法
• • • 快速排序
    • 第kkk个数
    • 归并排序
    • 逆序对数
    • 数的范围
    • 三次方根
    • 高精加
    • 高精减
    • 高精乘
    • 高精除
    • 前缀和
    • 矩阵前缀和
    • 差分
    • 差分矩阵
    • 最长连续不重复子序列
    • 数组元素的目标和
    • 二进制中1的个数
    • 区间和离散化
    • 区间合并
  • 数据结构
  • • 单调栈
    • 滑动窗口
    • KMP
    • Trie
    • 最大异或对
    • 并查集
    • 连通块中点的数量
    • 堆排序
    • 模拟堆
    • 字符串哈希
  • 搜索与图论
  • • 全排列
    • 组合型枚举
    • 八皇后
    • 走迷宫
    • 树的重心
    • 拓扑排序
    • 八数码
    • 解数独
    • 堆优化Dijkstra
    • SPFA
    • SPFA判负环
    • Bellman-Ford
    • Prim
    • Kruskal
    • 染色法判定二分图
    • 匈牙利算法
  • 数论
  • • 线性筛
    • 分解质因数
    • 试除法求约数
    • 约数个数
    • 约数之和
    • gcd
    • 欧拉函数
    • 筛法欧拉函数
    • 快速幂
    • 快速幂求逆元
    • 扩展欧几里得算法
    • 线性同余方程
    • 扩展中国剩余定理
    • 同余方程
    • 斐波那契(矩阵快速幂)
    • 高斯消元
    • 组合数
    • 卡特兰数
    • 能被整除的数
    • 龟速乘法
  • DP
  • • 01背包
    • 完全背包
    • 多重背包
    • 分组背包问题
    • 数字三角形
    • 石子合并
    • lis
    • 整数划分
    • 1050. 鸣人的影分身
    • NOIP2001数字划分
    • 滑雪
    • 没有上司的舞会
    • 最短Hamilton路径
    • 蒙德里安的梦想
    • 计数问题
    • Nim游戏
  • 贪心
  • • 区间选点
    • 最大不相交区间数量
    • 区间分组
    • 区间覆盖
    • 合并果子
    • 排队打水
    • 货仓选址
    • 耍杂技的牛
    • 判断子序列
    • 表达式求值
  • 上机课
  • • 进制转换
    • 3374. 进制转换2
    • 重排链表
    • 打印日期
    • 日期累加
    • 二叉树的带权路径长度
    • 二叉排序树
    • 表达式树
    • 未出现过的最小正整数
    • 三元组的最小距离
    • 众数
    • 玛雅人的密码
    • 等差数列
    • 3441. 重复者
    • 3382. 整数拆分
    • 位操作练习
    • 最小面积子矩阵
    • 矩阵幂
    • C翻转
    • 最长平衡串
• Python
• • • 差
    • 倍数
    • 零食
    • 字符串长度
    • 递增序列
    • 质数
    • 数组的右上
    • 蛇形矩阵
    • 排列
    • a+b
    • 行内数组求和
    • 字符串排序

基础算法

快速排序

#include 
using namespace std;
const int N = 100010;
int q[N];
void quick_sort(int q[], int l, int r){if (l >= r) return;int i = l - 1, j = r + 1, x = q[l + r >> 1];while (i < j){do i ++ ; while (q[i] < x);do j -- ; while (q[j] > x);if (i < j) swap(q[i], q[j]);}quick_sort(q, l, j);quick_sort(q, j + 1, r);
}
int main(){int n;scanf("%d", &n);for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);quick_sort(q, 0, n - 1);for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);return 0;
}

第kkk个数

#include 
using namespace std;
const int N = 100010;
int q[N];
int quick_sort(int q[], int l, int r, int k){if (l >= r) return q[l];int i = l - 1, j = r + 1, x = q[l + r >> 1];while (i < j){do i ++ ; while (q[i] < x);do j -- ; while (q[j] > x);if (i < j) swap(q[i], q[j]);}if (j - l + 1 >= k) return quick_sort(q, l, j, k);else return quick_sort(q, j + 1, r, k - (j - l + 1));
}
int main(){int n, k;scanf("%d%d", &n, &k);for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);cout << quick_sort(q, 0, n - 1, k) << endl;return 0;
}

归并排序

#include 
using namespace std;
const int N = 1e5 + 10;
int a[N], tmp[N];
void merge_sort(int q[], int l, int r){if (l >= r) return;int mid = l + r >> 1;merge_sort(q, l, mid), merge_sort(q, mid + 1, r);int k = 0, i = l, j = mid + 1;while (i <= mid && j <= r)if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];else tmp[k ++ ] = q[j ++ ];while (i <= mid) tmp[k ++ ] = q[i ++ ];while (j <= r) tmp[k ++ ] = q[j ++ ];for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}
int main(){int n;scanf("%d", &n);for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);merge_sort(a, 0, n - 1);for (int i = 0; i < n; i ++ ) printf("%d ", a[i]);return 0;
}

逆序对数

#include 
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N], tmp[N];
LL merge_sort(int q[], int l, int r){if (l >= r) return 0;int mid = l + r >> 1;LL res = merge_sort(q, l, mid) + merge_sort(q, mid + 1, r);int k = 0, i = l, j = mid + 1;while (i <= mid && j <= r)if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];else{res += mid - i + 1;tmp[k ++ ] = q[j ++ ];}while (i <= mid) tmp[k ++ ] = q[i ++ ];while (j <= r) tmp[k ++ ] = q[j ++ ];for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];return res;
}
int main(){int n;scanf("%d", &n);for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);cout << merge_sort(a, 0, n - 1) << endl;return 0;
}

数的范围

#include 
using namespace std;
const int N = 100010;
int n, m;
int q[N];
int main(){scanf("%d%d", &n, &m);for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);while (m -- ){int x;scanf("%d", &x);int l = 0, r = n - 1;while (l < r){int mid = l + r >> 1;if (q[mid] >= x) r = mid;else l = mid + 1;}if (q[l] != x) cout << "-1 -1" << endl;else{cout << l << ' ';int l = 0, r = n - 1;while (l < r){int mid = l + r + 1 >> 1;if (q[mid] <= x) l = mid;else r = mid - 1;}cout << l << endl;}}return 0;
}

三次方根

#include 
using namespace std;
int main(){double x;cin >> x;double l = -100, r = 100;while (r - l > 1e-8){double mid = (l + r) / 2;if (mid * mid * mid >= x) r = mid;else l = mid;}printf("%.6lf\n", l);return 0;
}

高精加

#include 
#include 
using namespace std;
vector add(vector &A, vector &B){if (A.size() < B.size()) return add(B, A);vector C;int t = 0;for (int i = 0; i < A.size(); i ++ ){t += A[i];if (i < B.size()) t += B[i];C.push_back(t % 10);t /= 10;}if (t) C.push_back(t);return C;
}
int main(){string a, b;vector A, B;cin >> a >> b;for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');auto C = add(A, B);for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];cout << endl;return 0;
}

高精减

#include 
#include 
using namespace std;
bool cmp(vector &A, vector &B){if (A.size() != B.size()) return A.size() > B.size();for (int i = A.size() - 1; i >= 0; i -- )if (A[i] != B[i])return A[i] > B[i];return true;
}
vector sub(vector &A, vector &B){vector C;for (int i = 0, t = 0; i < A.size(); i ++ ){t = A[i] - t;if (i < B.size()) t -= B[i];C.push_back((t + 10) % 10);if (t < 0) t = 1;else t = 0;}while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}
int main(){string a, b;vector A, B;cin >> a >> b;for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');vector C;if (cmp(A, B)) C = sub(A, B);else C = sub(B, A), cout << '-';for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];cout << endl;return 0;
}

高精乘

#include 
#include 
using namespace std;
vector mul(vector &A, int b){vector C;int t = 0;for (int i = 0; i < A.size() || t; i ++ ){if (i < A.size()) t += A[i] * b;C.push_back(t % 10);t /= 10;}while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}
int main(){string a;int b;cin >> a >> b;vector A;for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');auto C = mul(A, b);for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);return 0;
}

高精除

#include 
#include 
#include 
using namespace std;
vector div(vector &A, int b, int &r){vector C;r = 0;for (int i = A.size() - 1; i >= 0; i -- ){r = r * 10 + A[i];C.push_back(r / b);r %= b;}reverse(C.begin(), C.end());while (C.size() > 1 && C.back() == 0) C.pop_back();return C;
}
int main(){string a;vector A;int B;cin >> a >> B;for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');int r;auto C = div(A, B, r);for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];cout << endl << r << endl;return 0;
}

前缀和

#include 
using namespace std;
const int N = 100010;
int n, m;
int a[N], s[N];
int main(){scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i]; // 前缀和的初始化while (m -- ){int l, r;scanf("%d%d", &l, &r);printf("%d\n", s[r] - s[l - 1]); // 区间和的计算}return 0;
}

矩阵前缀和

#include 
using namespace std;
const int N = 1010;
int n, m, q;
int s[N][N];
int main(){scanf("%d%d%d", &n, &m, &q);for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ )scanf("%d", &s[i][j]);for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ )s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];while (q -- ){int x1, y1, x2, y2;scanf("%d%d%d%d", &x1, &y1, &x2, &y2);printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);}return 0;
}

差分

#include 
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N];
void insert(int l, int r, int c){b[l] += c;b[r + 1] -= c;
}
int main(){scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);for (int i = 1; i <= n; i ++ ) insert(i, i, a[i]);while (m -- ){int l, r, c;scanf("%d%d%d", &l, &r, &c);insert(l, r, c);}for (int i = 1; i <= n; i ++ ) b[i] += b[i - 1];for (int i = 1; i <= n; i ++ ) printf("%d ", b[i]);return 0;
}

差分矩阵

#include 
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N], b[N][N];
void insert(int x1, int y1, int x2, int y2, int c){b[x1][y1] += c;b[x2 + 1][y1] -= c;b[x1][y2 + 1] -= c;b[x2 + 1][y2 + 1] += c;
}
int main(){scanf("%d%d%d", &n, &m, &q);for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ )scanf("%d", &a[i][j]);for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ )insert(i, j, i, j, a[i][j]);while (q -- ){int x1, y1, x2, y2, c;cin >> x1 >> y1 >> x2 >> y2 >> c;insert(x1, y1, x2, y2, c);}for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ )b[i][j] += b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1];for (int i = 1; i <= n; i ++ ){for (int j = 1; j <= m; j ++ ) printf("%d ", b[i][j]);puts("");}return 0;
}

最长连续不重复子序列

#include 
using namespace std;
const int N = 100010;
int n;
int q[N], s[N];
int main(){scanf("%d", &n);for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);int res = 0;for (int i = 0, j = 0; i < n; i ++ ){s[q[i]] ++ ;while (j < i && s[q[i]] > 1) s[q[j ++ ]] -- ;res = max(res, i - j + 1);}cout << res << endl;return 0;
}

数组元素的目标和

#include 
using namespace std;
const int N = 1e5 + 10;
int n, m, x;
int a[N], b[N];
int main(){scanf("%d%d%d", &n, &m, &x);for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);for (int i = 0, j = m - 1; i < n; i ++ ){while (j >= 0 && a[i] + b[j] > x) j -- ;if (j >= 0 && a[i] + b[j] == x) cout << i << ' ' << j << endl;}return 0;
}

二进制中1的个数

#include 
using namespace std;
int main(){int n;scanf("%d", &n);while (n -- ){int x, s = 0;scanf("%d", &x);for (int i = x; i; i -= i & -i) s ++ ;printf("%d ", s);}return 0;
}

区间和离散化

#include 
#include 
#include 
using namespace std;
typedef pair PII;
const int N = 300010;
int n, m;
int a[N], s[N];
vector alls;
vector add, query;
int find(int x){int l = 0, r = alls.size() - 1;while (l < r){int mid = l + r >> 1;if (alls[mid] >= x) r = mid;else l = mid + 1;}return r + 1;
}
int main(){cin >> n >> m;for (int i = 0; i < n; i ++ ){int x, c;cin >> x >> c;add.push_back({x, c});alls.push_back(x);}for (int i = 0; i < m; i ++ ){int l, r;cin >> l >> r;query.push_back({l, r});alls.push_back(l);alls.push_back(r);}// 去重sort(alls.begin(), alls.end());alls.erase(unique(alls.begin(), alls.end()), alls.end());// 处理插入for (auto item : add){int x = find(item.first);a[x] += item.second;}// 预处理前缀和for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i];// 处理询问for (auto item : query){int l = find(item.first), r = find(item.second);cout << s[r] - s[l - 1] << endl;}return 0;
}

区间合并

#include 
#include 
#include 
using namespace std;
typedef pair PII;
void merge(vector &segs){vector res;sort(segs.begin(), segs.end());int st = -2e9, ed = -2e9;for (auto seg : segs)if (ed < seg.first){if (st != -2e9) res.push_back({st, ed});st = seg.first, ed = seg.second;}else ed = max(ed, seg.second);if (st != -2e9) res.push_back({st, ed});segs = res;
}
int main(){int n;scanf("%d", &n);vector segs;for (int i = 0; i < n; i ++ ){int l, r;scanf("%d%d", &l, &r);segs.push_back({l, r});}merge(segs);cout << segs.size() << endl;return 0;
}

数据结构

单调栈

给定一个长度为 NNN的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。

#include
#include
using namespace std;
stack stk;
const int N = 100005;
int arr[N];
int main() {int n;cin >> n;for (int i = 0; i < n; i++)cin >> arr[i];for (int i = 0; i < n; i++) {while (!stk.empty()&&arr[i] <= stk.top())stk.pop();if (stk.empty())cout << -1 << " ";else cout << stk.top() << " ";stk.push(arr[i]);}return 0;
}

滑动窗口

你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

#include
#include
using namespace std;
deque dq;
const int N = 1000005;
int arr[N];
int main() {int n, k;cin >> n >> k;for (int i = 0; i < n; i++)cin >> arr[i];for (int i = 0; i < n; i++) {if (!dq.empty() && i - k + 1 > dq.front())dq.pop_front();while (!dq.empty() && arr[dq.back()] >= arr[i])dq.pop_back();dq.push_back(i);if (i >= k - 1)cout << arr[dq.front()]<<" ";}dq.clear();cout << endl;for (int i = 0; i < n; i++) {if (!dq.empty() && i - k + 1 > dq.front())dq.pop_front();while (!dq.empty() && arr[dq.back()] <= arr[i])dq.pop_back();dq.push_back(i);if (i >= k - 1) cout << arr[dq.front()] << " ";}return 0;
}

KMP

#include 
using namespace std;
const int N = 100010, M = 1000010;
int n, m;
int ne[N];
char s[M], p[N];
int main(){cin >> n >> p + 1 >> m >> s + 1;for (int i = 2, j = 0; i <= n; i ++ ){while (j && p[i] != p[j + 1]) j = ne[j];if (p[i] == p[j + 1]) j ++ ;ne[i] = j;}for (int i = 1, j = 0; i <= m; i ++ ){while (j && s[i] != p[j + 1]) j = ne[j];if (s[i] == p[j + 1]) j ++ ;if (j == n){printf("%d ", i - n);j = ne[j];}}return 0;
}
/*下标从0开始
#include 
#include 
#include 
using namespace std;
const int N = 1000010;
int n, m;
char s[N], p[N];
int ne[N];
int main(){cin >> m >> p >> n >> s;ne[0] = -1;for (int i = 1, j = -1; i < m; i ++ ){while (j >= 0 && p[j + 1] != p[i]) j = ne[j];if (p[j + 1] == p[i]) j ++ ;ne[i] = j;}for (int i = 0, j = -1; i < n; i ++ ){while (j != -1 && s[i] != p[j + 1]) j = ne[j];if (s[i] == p[j + 1]) j ++ ;if (j == m - 1){cout << i - j << ' ';j = ne[j];}}return 0;
}

Trie

#include 
using namespace std;
const int N = 100010;
int son[N][26], cnt[N], idx;
char str[N];
void insert(char *str){int p = 0;for (int i = 0; str[i]; i ++ ){int u = str[i] - 'a';if (!son[p][u]) son[p][u] = ++ idx;p = son[p][u];}cnt[p] ++ ;
}
int query(char *str){int p = 0;for (int i = 0; str[i]; i ++ ){int u = str[i] - 'a';if (!son[p][u]) return 0;p = son[p][u];}return cnt[p];
}
int main(){int n;scanf("%d", &n);while (n -- ){char op[2];scanf("%s%s", op, str);if (*op == 'I') insert(str);else printf("%d\n", query(str));}return 0;
}

最大异或对

#include 
#include 
using namespace std;
const int N = 100010, M = 3100010;
int n;
int a[N], son[M][2], idx;
void insert(int x){int p = 0;for (int i = 30; i >= 0; i -- ){int &s = son[p][x >> i & 1];if (!s) s = ++ idx;p = s;}
}
int search(int x){int p = 0, res = 0;for (int i = 30; i >= 0; i -- ){int s = x >> i & 1;if (son[p][!s]){res += 1 << i;p = son[p][!s];}else p = son[p][s];}return res;
}
int main(){scanf("%d", &n);for (int i = 0; i < n; i ++ ){scanf("%d", &a[i]);insert(a[i]);}int res = 0;for (int i = 0; i < n; i ++ ) res = max(res, search(a[i]));printf("%d\n", res);return 0;
}

并查集

#include 
using namespace std;
const int N = 100010;
int p[N];
int find(int x){if (p[x] != x) p[x] = find(p[x]);return p[x];
}
int main(){int n, m;scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++ ) p[i] = i;while (m -- ){char op[2];int a, b;scanf("%s%d%d", op, &a, &b);if (*op == 'M') p[find(a)] = find(b);else{if (find(a) == find(b)) puts("Yes");else puts("No");}}return 0;
}

连通块中点的数量

#include 
using namespace std;
const int N = 100010;
int n, m;
int p[N], cnt[N];
int find(int x){if (p[x] != x) p[x] = find(p[x]);return p[x];
}
int main(){cin >> n >> m;for (int i = 1; i <= n; i ++ ){p[i] = i;cnt[i] = 1;}while (m -- ){string op;int a, b;cin >> op;if (op == "C"){cin >> a >> b;a = find(a), b = find(b);if (a != b){p[a] = b;cnt[b] += cnt[a];}}else if (op == "Q1"){cin >> a >> b;if (find(a) == find(b)) puts("Yes");else puts("No");}else{cin >> a;cout << cnt[find(a)] << endl;}}return 0;
}

堆排序

#include 
#include 
using namespace std;
const int N = 100010;
int n, m;
int h[N], cnt;
void down(int u){int t = u;if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;if (u != t){swap(h[u], h[t]);down(t);}
}
int main(){scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);cnt = n;for (int i = n / 2; i; i -- ) down(i);while (m -- ){printf("%d ", h[1]);h[1] = h[cnt -- ];down(1);}puts("");return 0;
}

模拟堆

维护一个集合，初始时集合为空，支持如下几种操作：
I x，插入一个数 xxx；
PM，输出当前集合中的最小值；
DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
D k，删除第 kkk 个插入的数；
C k x，修改第 kkk 个插入的数，将其变为 xxx；
现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。

#include
#include
using namespace std;
const int N=1e5+10;
int h[N];   //堆
int ph[N];  //存放第k个插入点的下标
int hp[N];  //存放堆中点的插入次序
int cur_size;   //size 记录的是堆当前的数据多少
//这个交换过程其实有那么些绕 但关键是理解 如果hp[u]=k 则ph[k]=u 的映射关系
//之所以要进行这样的操作是因为 经过一系列操作 堆中的元素并不会保持原有的插入顺序
//从而我们需要对应到原先第K个堆中元素
//如果理解这个原理 那么就能明白其实三步交换的顺序是可以互换 
//h,hp,ph之间两两存在映射关系 所以交换顺序的不同对结果并不会产生影响
void heap_swap(int u,int v){   swap(h[u],h[v]); swap(hp[u],hp[v]);     swap(ph[hp[u]],ph[hp[v]]);            
}
void down(int u){int t=u;if(u*2<=cur_size&&h[t]>h[u*2]) t=u*2;if(u*2+1<=cur_size&&h[t]>h[u*2+1])  t=u*2+1;if(u!=t){heap_swap(u,t);down(t);}
}
void up(int u){if(u/2>0&&h[u]>1);}
}
int main(){int n;cin>>n;int m=0;      //m用来记录插入的数的个数//注意m的意义与cur_size是不同的 cur_size是记录堆中当前数据的多少//对应上文 m即是hp中应该存的值while(n--){string op;int k,x;cin>>op;if(op=="I"){cin>>x;m++;h[++cur_size]=x;ph[m]=cur_size;hp[cur_size]=m;//down(size);up(cur_size);}else if(op=="PM")    cout<>k;int u=ph[k];//这里一定要用u=ph[k]保存第k个插入点的下标heap_swap(u,cur_size);//因为在此处heap_swap操作后ph[k]的值已经发生 cur_size--;//如果在up,down操作中仍然使用ph[k]作为参数就会发生错误up(u);down(u);}else if(op=="C"){cin>>k>>x;h[ph[k]]=x;//此处由于未涉及heap_swap操作且下面的up、down操作只会发生一个所以down(ph[k]);//所以可直接传入ph[k]作为参数up(ph[k]);}}return 0;
}

字符串哈希

#include 
#include 
using namespace std;
typedef unsigned long long ULL;
const int N = 100010, P = 131;
int n, m;
char str[N];
ULL h[N], p[N];
ULL get(int l, int r){return h[r] - h[l - 1] * p[r - l + 1];
}
int main(){scanf("%d%d", &n, &m);scanf("%s", str + 1);p[0] = 1;for (int i = 1; i <= n; i ++ ){h[i] = h[i - 1] * P + str[i];p[i] = p[i - 1] * P;}while (m -- ){int l1, r1, l2, r2;scanf("%d%d%d%d", &l1, &r1, &l2, &r2);if (get(l1, r1) == get(l2, r2)) puts("Yes");else puts("No");}return 0;
}

搜索与图论

全排列

#include 
using namespace std;
const int N = 10;
int n;
int path[N];
void dfs(int u, int state){if (u == n){for (int i = 0; i < n; i ++ ) printf("%d ", path[i]);puts("");return;}for (int i = 0; i < n; i ++ )if (!(state >> i & 1)){path[u] = i + 1;dfs(u + 1, state + (1 << i));}
}
int main(){scanf("%d", &n);dfs(0, 0);return 0;
}

组合型枚举

#include
#include
using namespace std;
bool chosen[30];
int n, m;
vector nums;
void dfs(int pos) {if (nums.size() > m || nums.size() + n - pos + 1 < m)return;if (nums.size() == m) {for (int i = 0; i < nums.size(); i++)cout << nums[i]<<" ";cout << endl;return;}nums.push_back(pos);dfs(pos + 1);nums.pop_back();dfs(pos + 1);
}
int main() {cin >> n >> m;dfs(1);return 0;
}

八皇后

#include 
using namespace std;
const int N = 20;
int n;
char g[N][N];
bool col[N], dg[N], udg[N];
void dfs(int u){if (u == n){for (int i = 0; i < n; i ++ ) puts(g[i]);puts("");return;}for (int i = 0; i < n; i ++ )if (!col[i] && !dg[u + i] && !udg[n - u + i]){g[u][i] = 'Q';col[i] = dg[u + i] = udg[n - u + i] = true;dfs(u + 1);col[i] = dg[u + i] = udg[n - u + i] = false;g[u][i] = '.';}
}
int main(){cin >> n;for (int i = 0; i < n; i ++ )for (int j = 0; j < n; j ++ )g[i][j] = '.';dfs(0);return 0;
}

走迷宫

#include 
#include 
#include 
#include 
using namespace std;
typedef pair PII;
const int N = 110;
int n, m;
int g[N][N], d[N][N];
int bfs(){queue q;memset(d, -1, sizeof d);d[0][0] = 0;q.push({0, 0});int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};while (q.size()){auto t = q.front();q.pop();for (int i = 0; i < 4; i ++ ){int x = t.first + dx[i], y = t.second + dy[i];if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1){d[x][y] = d[t.first][t.second] + 1;q.push({x, y});}}}return d[n - 1][m - 1];
}
int main(){cin >> n >> m;for (int i = 0; i < n; i ++ )for (int j = 0; j < m; j ++ )cin >> g[i][j];cout << bfs() << endl;return 0;
}

树的重心

重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。

#include
#include
#include
using namespace std;
const int N = 100005;
vector g[N];
int n;
int st[N];
int ans = N;
int dfs(int u) {st[u] = true;int sum = 1, res = 0;for (auto node : g[u]) {if (!st[node]) {int s = dfs(node);res = max(res, s);sum += s;}}res = max(res, n - sum);ans = min(ans, res);return sum;
}
int main() {cin >> n;for(int i=0;i> a >> b;g[a].push_back(b);g[b].push_back(a);}dfs(1);cout << ans;return 0;
}

拓扑排序

#include
#include
#include
using namespace std;
const int N = 100010;
int n, m;
vector graph[N];
vector path;
int ind[N];//入度
bool toposort() {int indnode = 0;queue q;for (int i = 1; i <= n; i++) {if (ind[i] == 0) {indnode = i;q.push(i);}}if (indnode == 0)return false;while (!q.empty()) {int cur = q.front();q.pop();path.push_back(cur);for (auto node : graph[cur]) {ind[node]--;if (ind[node] == 0)q.push(node);}}for (int i = 1; i <= n; i++)if (ind[i] > 0)return false;return true;
}
int main() {cin >> n >> m;while (m--) {int x, y;cin >> x >> y;graph[x].push_back(y);ind[y]++;}if (toposort()) {for (auto node : path)cout << node << " ";}else cout << -1;return 0;
}

八数码

#include
#include
#include
#include

解数独

#include 
#include 
#include 
using namespace std;
const int N = 9, M = 1 << N;
int ones[M], map[M];
int row[N], col[N], cell[3][3];
char str[100];
void init(){for (int i = 0; i < N; i ++ )row[i] = col[i] = (1 << N) - 1;for (int i = 0; i < 3; i ++ )for (int j = 0; j < 3; j ++ )cell[i][j] = (1 << N) - 1;
}
void draw(int x, int y, int t, bool is_set){if (is_set) str[x * N + y] = '1' + t;else str[x * N + y] = '.';int v = 1 << t;if (!is_set) v = -v;row[x] -= v;col[y] -= v;cell[x / 3][y / 3] -= v;
}
int lowbit(int x){return x & -x;
}
int get(int x, int y){return row[x] & col[y] & cell[x / 3][y / 3];
}
bool dfs(int cnt){if (!cnt) return true;int minv = 10;int x, y;for (int i = 0; i < N; i ++ )for (int j = 0; j < N; j ++ )if (str[i * N + j] == '.'){int state = get(i, j);if (ones[state] < minv){minv = ones[state];x = i, y = j;}}int state = get(x, y);for (int i = state; i; i -= lowbit(i)){int t = map[lowbit(i)];draw(x, y, t, true);if (dfs(cnt - 1)) return true;draw(x, y, t, false);}return false;
}
int main(){for (int i = 0; i < N; i ++ ) map[1 << i] = i;for (int i = 0; i < 1 << N; i ++ )for (int j = 0; j < N; j ++ )ones[i] += i >> j & 1;while (cin >> str, str[0] != 'e'){init();int cnt = 0;for (int i = 0, k = 0; i < N; i ++ )for (int j = 0; j < N; j ++, k ++ )if (str[k] != '.'){int t = str[k] - '1';draw(i, j, t, true);}else cnt ++ ;dfs(cnt);puts(str);}return 0;
}

堆优化Dijkstra

#include
#include
#include
#include
using namespace std;
int t,c,ts,te;
int ans=0;
typedef pair PII;
priority_queue,greater > q;
int st[2505];
int dist[2505];
vector g[2505];
void dijkstra(){memset(dist,0x3f3f3f3f,sizeof dist);dist[ts]=0;q.push({0,ts});while(!q.empty()){auto [d,cur]=q.top();q.pop();if (st[cur])continue;st[cur]=1;for(auto node:g[cur]){auto [d,next]=node;if (d+dist[cur]>t>>c>>ts>>te;for(int i=1;i<=c;i++){int rs,re,ci;cin>>rs>>re>>ci;g[rs].push_back({ci,re});g[re].push_back({ci,rs});}dijkstra();cout<

#include
#include
#include
#include
using namespace std;
int n, m;
const int N = 100005;
int dist[N];
typedef  pair PII;//first表示指向点，second表示距离
vector graph[N];
void spfa() {dist[1] = 0;queue q;q.push(1);while (!q.empty()) {int curnode = q.front();q.pop();for (auto node : graph[curnode]) {if (dist[node.first] > dist[curnode] + node.second) {dist[node.first] = dist[curnode] + node.second;q.push(node.first);}}}
}
int main() {cin >> n >> m;while (m--) {int x, y, z;cin >> x >> y >> z;graph[x].push_back({ y,z });}memset(dist, 0x3f3f3f3f, sizeof dist);spfa();if (dist[n] > 0x3f3f3f3f / 2)cout << "impossible";elsecout << dist[n];return 0;
}

#include
#include
#include
using namespace std;
int n, m;
const int N = 100005;
int cnt[N];
int dist[N];
typedef  pair PII;//first表示指向点，second表示距离
vector graph[N];
bool spfa() {queue q;for(int i=1;i<=n;i++)q.push(i);while (!q.empty()) {int curnode = q.front();q.pop();for (auto node : graph[curnode]) {if (dist[node.first] > dist[curnode] + node.second) {dist[node.first] = dist[curnode] + node.second;cnt[node.first]=cnt[curnode]+1;if (cnt[node.first] >= n)return true;q.push(node.first);}}}return false;
}
int main() {cin >> n >> m;while (m--) {int x, y, z;cin >> x >> y >> z;graph[x].push_back({ y,z });}if (spfa())cout << "Yes";elsecout << "No";return 0;
}

#include
#include
using namespace std;
int n, m, k;
struct Edge {int x, y, z;
};
Edge edges[10005];
int dist[505];
int backup[505];
int main() {cin >> n >> m >> k;memset(dist, 0x3f3f3f3f, sizeof dist);memset(backup, 0x3f3f3f3f, sizeof backup);for(int i=0;i> x >> y >> z;edges[i] = { x,y,z };}dist[1] = 0;while (k--) {for (int i = 1; i <= n; i++)backup[i] = dist[i];for (int i = 0; i < m; i++) dist[edges[i].y] = min( dist[edges[i].y],backup[edges[i].x] + edges[i].z );}if (dist[n] >= 0x3f3f3f3f / 2)cout << "impossible";elsecout << dist[n];return 0;
}

#include
#include
using namespace std;
const int N = 505;
int graph[N][N];
int dist[N];
int s[N];
int n, m;
int res = 0;
void prim() {s[1] = true;dist[1] = 0;for (int i = 1; i <= n; i++)dist[i] = graph[1][i];for (int i = 1; i <= n; i++) {int curnode = 0;for (int j = 1; j <= n; j++) {if (!s[j] && (curnode==0||dist[j] < dist[curnode]))curnode = j;}if (curnode&&dist[curnode] == 0x3f3f3f3f) {res = 0x3f3f3f3f;return;}if (curnode) {s[curnode] = true;res += dist[curnode];for (int j = 1; j <= n; j++)if (!s[j] && dist[j] >  graph[curnode][j])dist[j] =  graph[curnode][j];}}
}
int main() {cin >> n >> m;memset(graph, 0x3f3f3f3f, sizeof graph);memset(dist, 0x3f3f3f3f, sizeof dist);while (m--) {int x, y, z;cin >> x >> y >> z;if (z < graph[x][y])graph[x][y] =graph[y][x]= z;}for (int i = 0; i <= n; i++)graph[i][i] = 0;prim();if (res < 0x3f3f3f3f)cout << res;elsecout << "impossible";return 0;
}

#include
#include
using namespace std;
const int N = 1000005;
struct edge {int u, v, w;bool operator <(const edge& b) const {return w < b.w;}
};
int p[N];
edge edges[N];
int find(int a) {if (a!= p[a]) p[a] = find(p[a]);else return p[a];
}
int main() {int n, m;cin >> n >> m;for (int i = 0; i < m; i++) {int u, v, w;cin >> u >> v >> w;if (u!=v)edges[i] = { u,v,w };}for (int i = 0; i <=n; i++)p[i] = i;sort(edges, edges + m);long long res = 0;int cnt = 0;for (int i = 0; i < m; i++) {int u = edges[i].u;int v = edges[i].v;int w = edges[i].w;u = find(u);v = find(v);if (u != v) {res += w;cnt++;p[find(u)] =v;}}if (cnt < n - 1)cout << "impossible";elsecout << res;return 0;
}

#include
#include
using namespace std;
const int N = 100005;
int color[N];
int res = true;
vector G[N];
void dfs(int i, int clr) {color[i] = clr;for (auto node : G[i]) {if(!color[node])dfs(node, 3 - clr);else if (color[node] == color[i]) {res = false;return;}}
}
int main() {int n, m;cin >> n >> m;while (m--){int u, v;cin >> u >> v;if (u != v) {G[u].push_back(v);G[v].push_back(u);}}for (int i = 1; i <= n; i++) {if(!color[i])dfs(i, 1);}if (res)cout << "Yes";elsecout << "No";return 0;
}

#include
#include
#include
using namespace std;
const int N = 1005;
vector graph[N];
int match[N];
int st[N];
bool find(int x) {for (auto node : graph[x]) {if (!st[node]) {st[node] = true;if (!match[node] || find(match[node])) {match[node]=x;return true;}}}return false;
}
int main() {int n1, n2, m;cin >> n1 >> n2 >> m;while (m--) {int u, v;cin >> u >> v;graph[u].push_back(v);}int res = 0;for (int i = 1; i <= n1; i++) {memset(st, false, sizeof st);if (find(i))res++;}cout << res << endl;return 0;
}

#include 
#include 
using namespace std;
const int N= 1000010;
int primes[N], cnt;
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 main(){int n;cin >> n;get_primes(n);cout << cnt << endl;return 0;
}

#include 
#include 
using namespace std;
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;
}
int main(){int n;cin >> n;while (n -- ){int x;cin >> x;divide(x);}return 0;
}

#include 
#include 
#include 
using namespace std;
vector get_divisors(int x){vector 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;
}
int main(){int n;cin >> n;while (n -- ){int x;cin >> x;auto res = get_divisors(x);for (auto x : res) cout << x << ' ';cout << endl;}return 0;
}

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int N = 110, mod = 1e9 + 7;
int main(){int n;cin >> n;unordered_map primes;while (n -- ){int x;cin >> 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 p : primes) res = res * (p.second + 1) % mod;cout << res << endl;return 0;
}

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int N = 110, mod = 1e9 + 7;
int main(){int n;cin >> n;unordered_map primes;while (n -- ){int x;cin >> 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 p : primes){LL a = p.first, b = p.second;LL t = 1;while (b -- ) t = (t * a + 1) % mod;res = res * t % mod;}cout << res << endl;return 0;
}

#include 
#include 
using namespace std;
int gcd(int a, int b){return b ? gcd(b, a % b) : a;
}
int main(){int n;cin >> n;while (n -- ){int a, b;scanf("%d%d", &a, &b);printf("%d\n", gcd(a, b));}return 0;
}

#include 
using namespace std;
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;
}
int main(){int n;cin >> n;while (n -- ){int x;cin >> x;cout << phi(x) << endl;}return 0;
}

#include 
using namespace std;
typedef long long LL;
const int N = 1000010;
int primes[N], cnt;
int euler[N];
bool st[N];
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);}}
}
int main(){int n;cin >> n;get_eulers(n);LL res = 0;for (int i = 1; i <= n; i ++ ) res += euler[i];cout << res << endl;return 0;
}

#include 
#include 
using namespace std;
typedef long long LL;
LL qmi(int a, int b, int p){LL res = 1 % p;while (b){if (b & 1) res = res * a % p;a = a * (LL)a % p;b >>= 1;}return res;
}
int main(){int n;scanf("%d", &n);while (n -- ){int a, b, p;scanf("%d%d%d", &a, &b, &p);printf("%lld\n", qmi(a, b, p));}return 0;
}

#include 
#include 
using namespace std;
typedef long long LL;
LL qmi(int a, int b, int p){LL res = 1;while (b){if (b & 1) res = res * a % p;a = a * (LL)a % p;b >>= 1;}return res;
}
int main(){int n;scanf("%d", &n);while (n -- ){int a, p;scanf("%d%d", &a, &p);if (a % p == 0) puts("impossible");else printf("%lld\n", qmi(a, p - 2, p));}return 0;
}

#include 
#include 
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;scanf("%d", &n);while (n -- ){int a, b;scanf("%d%d", &a, &b);int x, y;exgcd(a, b, x, y);printf("%d %d\n", x, y);}return 0;
}

#include 
#include 
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;scanf("%d", &n);while (n -- ){int a, b, m;scanf("%d%d%d", &a, &b, &m);int x, y;int d = exgcd(a, m, x, y);if (b % d) puts("impossible");else printf("%d\n", (LL)b / d * x % m);}return 0;
}

#include 
#include 
using namespace std;
typedef long long LL;
int n;
LL exgcd(LL a, LL b, LL &x, LL &y){if(b == 0){x = 1, y = 0;return a;}LL d = exgcd(b, a % b, y, x);y -= a / b * x;return d;
}
LL inline mod(LL a, LL b){return ((a % b) + b) % b;
}
int main(){scanf("%d", &n);LL a1, m1;scanf("%lld%lld", &a1, &m1);for(int i = 1; i < n; i++){LL a2, m2, k1, k2;scanf("%lld%lld", &a2, &m2);LL d = exgcd(a1, -a2, k1, k2);if((m2 - m1) % d){ puts("-1"); return 0; }k1 = mod(k1 * (m2 - m1) / d, abs(a2 / d));m1 = k1 * a1 + m1;a1 = abs(a1 / d * a2);}printf("%lld\n", m1);return 0;
}

#include
typedef long long LL;
using namespace std;
LL exgcd(LL a,LL b,LL&x,LL&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(){LL a,b,x,y;cin>>a>>b;exgcd(a,b,x,y);cout<<(x%b+b)%b;return 0;
}

#include
typedef long long LL;
using namespace std;
LL n,m;
LL M[2][2]={{0,1},{1,1}
};
LL res[2]={1,0};
void mulrm(){LL ans[2]={0};for(LL i=0;i<2;i++)for(LL j=0;j<2;j++)ans[i]+=res[j]*M[i][j]%m;for(LL i=0;i<2;i++)res[i]=ans[i]%m;
}
void mulmm(){LL ans[2][2]={0};for(LL i=0;i<2;i++){for(LL j=0;j<2;j++){for(LL k=0;k<2;k++)ans[i][j]+=M[i][k]*M[k][j]%m;}}for(LL i=0;i<2;i++)for(LL j=0;j<2;j++)M[i][j]=ans[i][j]%m;
}
void qpow(LL n){while(n){if (n&1)mulrm();mulmm();n>>=1;}
}
int main(){cin>>n>>m;qpow(n+2);cout<

#include 
#include 
#include 
#include 
using namespace std;
const int N = 110;
const double eps = 1e-8;
int n;
double a[N][N];
int gauss(){  // 高斯消元，答案存于a[i][n]中，0 <= i < nint 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];  // 将当前行的首位变成1for (int i = r + 1; i < n; i ++ )  // 用当前行将下面所有的列消成0if (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; // 有唯一解
}
int main(){scanf("%d", &n);for (int i = 0; i < n; i ++ )for (int j = 0; j < n + 1; j ++ )scanf("%lf", &a[i][j]);int t = gauss();if (t == 2) puts("No solution");else if (t == 1) puts("Infinite group solutions");else{for (int i = 0; i < n; i ++ ){if (fabs(a[i][n]) < eps) a[i][n] = 0;  // 去掉输出 -0.00 的情况printf("%.2lf\n", a[i][n]);}}return 0;
}

#include 
#include 
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(){int n;init();scanf("%d", &n);while (n -- ){int a, b;scanf("%d%d", &a, &b);printf("%d\n", c[a][b]);}return 0;
}

#include 
#include 
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;scanf("%d", &n);while (n -- ){int a, b;scanf("%d%d", &a, &b);printf("%d\n", (LL)fact[a] * infact[b] % mod * infact[a - b] % mod);}return 0;
}

#include 
#include 
using namespace std;
typedef long long LL;
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 C(int a, int b, int p){if (b > a) return 0;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) % p;}return res;
}
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;
}
int main(){int n;cin >> n;while (n -- ){LL a, b;int p;cin >> a >> b >> p;cout << lucas(a, b, p) << endl;}return 0;
}

#include 
#include 
using namespace std;
typedef long long LL;
const int N = 100010, 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 = n * 2, 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;
}

#include 
#include 
using namespace std;
typedef long long LL;
const int N = 20;
int p[N];
int main(){int n, m;cin >> n >> m;for (int i = 0; i < m; i ++ ) cin >> p[i];int res = 0;for (int i = 1; i < 1 << m; i ++ ){int t = 1, s = 0;for (int j = 0; j < m; j ++ )if (i >> j & 1){if ((LL)t * p[j] > n){t = -1;break;}t *= p[j];s ++ ;}if (t != -1){if (s % 2) res += n / t;else res -= n / t;}}cout << res << endl;return 0;
}

#include
using namespace std;
typedef long long LL;
LL a,b,p;
LL qadd(LL a,LL b,LL p){LL res=0;while(b){if (b&1)res=(res+a)%p;a=(a+a)%p;b>>=1;}return res;
}
int main(){cin>>a>>b>>p;cout<

#include 
#include 
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main(){cin >> n >> m;for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];for (int i = 1; i <= n; i ++ )for (int j = m; j >= v[i]; j -- )f[j] = max(f[j], f[j - v[i]] + w[i]);cout << f[m] << endl;return 0;
}

#include 
#include 
using namespace std;
const int N = 1010;
int n, m;
int v[N], w[N];
int f[N];
int main(){cin >> n >> m;for (int i = 1; i <= n; i ++ ) cin >> v[i] >> w[i];for (int i = 1; i <= n; i ++ )for (int j = v[i]; j <= m; j ++ )f[j] = max(f[j], f[j - v[i]] + w[i]);cout << f[m] << endl;return 0;
}

#include
#include
using namespace std;
int dp[10005];
int v[1005];
int w[1005];
int s[1005];
int vf[10005], wf[10005];
int N, V;
int main() {cin >> N >> V;for (int i = 1; i <= N; i++)cin >> v[i] >> w[i]>>s[i];int idx = 0;for (int i = 1; i <= N; i++) {int cur = 1;int res = s[i];while (res>=cur) {res = res - cur;idx++;vf[idx] = cur * v[i];wf[idx] = cur * w[i];cur = cur * 2;}if (res>0) {idx++;vf[idx] = res * v[i];wf[idx] = res * w[i];}}for(int i=1;i<=idx;i++)for (int j = V; j >= vf[i]; j--) {dp[j] = max(dp[j], dp[j - vf[i]] + wf[i]);}cout << dp[V];return 0;
}

#include 
#include 
using namespace std;
const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];
int main(){cin >> n >> m;for (int i = 1; i <= n; i ++ ){cin >> s[i];for (int j = 0; j < s[i]; j ++ )cin >> v[i][j] >> w[i][j];}for (int i = 1; i <= n; i ++ )for (int j = m; j >= 0; j -- )for (int k = 0; k < s[i]; k ++ )if (v[i][k] <= j)f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);cout << f[m] << endl;return 0;
}

#include 
#include 
using namespace std;
const int N = 510, INF = 1e9;
int n;
int a[N][N];
int f[N][N];
int main(){scanf("%d", &n);for (int i = 1; i <= n; i ++ )for (int j = 1; j <= i; j ++ )scanf("%d", &a[i][j]);for (int i = 0; i <= n; i ++ )for (int j = 0; j <= i + 1; j ++ )f[i][j] = -INF;f[1][1] = a[1][1];for (int i = 2; i <= n; i ++ )for (int j = 1; j <= i; j ++ )f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);int res = -INF;for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);printf("%d\n", res);return 0;
}

#include 
#include 
using namespace std;
const int N = 310;
int n;
int s[N];
int f[N][N];
int main(){scanf("%d", &n);for (int i = 1; i <= n; i ++ ) scanf("%d", &s[i]);for (int i = 1; i <= n; i ++ ) s[i] += s[i - 1];for (int len = 2; len <= n; len ++ )for (int i = 1; i + len - 1 <= n; i ++ ){int l = i, r = i + len - 1;f[l][r] = 1e8;for (int k = l; k < r; k ++ )f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);}printf("%d\n", f[1][n]);return 0;
}

#include 
#include 
using namespace std;
const int N = 100010;
int n;
int a[N];
int q[N];
int main(){scanf("%d", &n);for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);int len = 0;for (int i = 0; i < n; i ++ ){int l = 0, r = len;while (l < r){int mid = l + r + 1 >> 1;if (q[mid] < a[i]) l = mid;else r = mid - 1;}len = max(len, r + 1);q[r + 1] = a[i];}printf("%d\n", len);return 0;
}

#include 
#include 
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n;
int f[N];
int main(){cin >> n;f[0] = 1;for (int i = 1; i <= n; i ++ )for (int j = i; j <= n; j ++ )f[j] = (f[j] + f[j - i]) % mod;cout << f[n] << endl;return 0;
}

#include 
#include 
using namespace std;
const int N = 1010, mod = 1e9 + 7;
int n;
int f[N][N];
int main(){cin >> n;f[1][1] = 1;for (int i = 2; i <= n; i ++ )for (int j = 1; j <= i; j ++ )f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;int res = 0;for (int i = 1; i <= n; i ++ ) res = (res + f[n][i]) % mod;cout << res << endl;return 0;
}

#include
#include
using namespace std;
int f[15][15];
int main(){int t;cin>>t;while(t--){int m,n;cin>>m>>n;memset(f,0,sizeof f);f[0][0]=1;//把m划分成n个数for(int i=0;i<=m;i++){for(int j=1;j<=n;j++){f[i][j]+=f[i][j-1];if (i>=j)f[i][j]+=f[i-j][j];}}cout<

#include
using namespace std;
int dp[205][10];
int main(){int n,k;cin>>n>>k;dp[0][0]=0;for(int i=0;i<=n;i++)dp[i][1]=1;for(int i=2;i<=n;i++){for(int j=1;j<=k;j++){dp[i][j]=dp[i-1][j-1];if(i>j)dp[i][j]+=dp[i-j][j];}}cout<

#include 
#include 
#include 
using namespace std;
const int N = 310;
int n, m;
int g[N][N];
int f[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dp(int x, int y){int &v = f[x][y];if (v != -1) return v;v = 1;for (int i = 0; i < 4; i ++ ){int a = x + dx[i], b = y + dy[i];if (a >= 1 && a <= n && b >= 1 && b <= m && g[x][y] > g[a][b])v = max(v, dp(a, b) + 1);}return v;
}
int main(){scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ )scanf("%d", &g[i][j]);memset(f, -1, sizeof f);int res = 0;for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ )res = max(res, dp(i, j));printf("%d\n", res);return 0;
}

#include
#include
using namespace std;
const int N=6005;
int f[N][2];
vector G[N];
bool st[N];
int H[N];
void dfs(int root){f[root][1]=H[root];//选自己for(auto node:G[root]){dfs(node);f[root][0]+=max(f[node][0],f[node][1]);//不选自己f[root][1]+=f[node][0];//选自己}
}
int main(){int n;cin>>n;for(int i=1;i<=n;i++)cin>>H[i];for(int i=0;i>u>>v;G[v].push_back(u);st[u]=1;}int root=0;for(int i=1;i<=n;i++){if (st[i]==0){root=i;break;}}dfs(root);cout<

#include 
#include 
#include 
using namespace std;
const int N = 20, M = 1 << N;
int n;
int w[N][N];
int f[M][N];
int main(){cin >> n;for (int i = 0; i < n; i ++ )for (int j = 0; j < n; j ++ )cin >> w[i][j];memset(f, 0x3f, sizeof f);f[1][0] = 0;for (int i = 0; i < 1 << n; i ++ )for (int j = 0; j < n; j ++ )if (i >> j & 1)for (int k = 0; k < n; k ++ )if (i >> k & 1)f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);cout << f[(1 << n) - 1][n - 1];return 0;
}

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int N = 12, M = 1 << N;
int n, m;
LL f[N][M];
vector state[M];
bool st[M];
int main(){while (cin >> n >> m, n || m){for (int i = 0; i < 1 << n; i ++ ){int cnt = 0;bool is_valid = true;for (int j = 0; j < n; j ++ )if (i >> j & 1){if (cnt & 1){is_valid = false;break;}cnt = 0;}else cnt ++ ;if (cnt & 1) is_valid = false;st[i] = is_valid;}for (int i = 0; i < 1 << n; i ++ ){state[i].clear();for (int j = 0; j < 1 << n; j ++ )if ((i & j) == 0 && st[i | j])state[i].push_back(j);}memset(f, 0, sizeof f);f[0][0] = 1;for (int i = 1; i <= m; i ++ )for (int j = 0; j < 1 << n; j ++ )for (auto k : state[j])f[i][j] += f[i - 1][k];cout << f[m][0] << endl;}return 0;
}

#include 
#include 
#include 
using namespace std;
const int N = 10;
/*
001~abc-1, 999
abc1. num[i] < x, 02. num[i] == x, 0~efg3. num[i] > x, 0~999
*/
int get(vector num, int l, int r){int res = 0;for (int i = l; i >= r; i -- ) res = res * 10 + num[i];return res;
}
int power10(int x){int res = 1;while (x -- ) res *= 10;return res;
}
int count(int n, int x){if (!n) return 0;vector num;while (n){num.push_back(n % 10);n /= 10;}n = num.size();int res = 0;for (int i = n - 1 - !x; i >= 0; i -- ){if (i < n - 1){res += get(num, n - 1, i + 1) * power10(i);if (!x) res -= power10(i);}if (num[i] == x) res += get(num, i - 1, 0) + 1;else if (num[i] > x) res += power10(i);}return res;
}
int main(){int a, b;while (cin >> a >> b , a){if (a > b) swap(a, b);for (int i = 0; i <= 9; i ++ )cout << count(b, i) - count(a - 1, i) << ' ';cout << endl;}return 0;
}

#include 
#include 
using namespace std;
/*
先手必胜状态：先手操作完，可以走到某一个必败状态
先手必败状态：先手操作完，走不到任何一个必败状态
先手必败状态：a1 ^ a2 ^ a3 ^ ... ^an = 0
先手必胜状态：a1 ^ a2 ^ a3 ^ ... ^an ≠ 0
*/
int main(){int n;scanf("%d", &n);int res = 0;for(int i = 0; i < n; i++) {int x;scanf("%d", &x);res ^= x;}if(res == 0) puts("No");else puts("Yes");
}

#include 
#include 
using namespace std;
const int N = 100010;
int n;
struct Range{int l, r;bool operator< (const Range &W)const{return r < W.r;}
}range[N];
int main(){scanf("%d", &n);for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r);sort(range, range + n);int res = 0, ed = -2e9;for (int i = 0; i < n; i ++ )if (range[i].l > ed){res ++ ;ed = range[i].r;}printf("%d\n", res);return 0;
}

#include 
#include 
using namespace std;
const int N = 100010;
int n;
struct Range{int l, r;bool operator< (const Range &W)const{return r < W.r;}
}range[N];
int main(){scanf("%d", &n);for (int i = 0; i < n; i ++ ) scanf("%d%d", &range[i].l, &range[i].r);sort(range, range + n);int res = 0, ed = -2e9;for (int i = 0; i < n; i ++ )if (ed < range[i].l){res ++ ;ed = range[i].r;}printf("%d\n", res);return 0;
}

#include 
#include 
#include 
using namespace std;
const int N = 100010;
int n;
struct Range{int l, r;bool operator< (const Range &W)const{return l < W.l;}
}range[N];
int main(){scanf("%d", &n);for (int i = 0; i < n; i ++ ){int l, r;scanf("%d%d", &l, &r);range[i] = {l, r};}sort(range, range + n);priority_queue, greater> heap;for (int i = 0; i < n; i ++ ){auto r = range[i];if (heap.empty() || heap.top() >= r.l) heap.push(r.r);else{heap.pop();heap.push(r.r);}}printf("%d\n", heap.size());return 0;
}

#include 
#include 
using namespace std;
const int N = 100010;
int n;
struct Range{int l, r;bool operator< (const Range &W)const{return l < W.l;}
}range[N];
int main(){int st, ed;scanf("%d%d", &st, &ed);scanf("%d", &n);for (int i = 0; i < n; i ++ ){int l, r;scanf("%d%d", &l, &r);range[i] = {l, r};}sort(range, range + n);int res = 0;bool success = false;for (int i = 0; i < n; i ++ ){int j = i, r = -2e9;while (j < n && range[j].l <= st){r = max(r, range[j].r);j ++ ;}if (r < st){res = -1;break;}res ++ ;if (r >= ed){success = true;break;}st = r;i = j - 1;}if (!success) res = -1;printf("%d\n", res);return 0;
}

#include 
#include 
#include 
using namespace std;
int main(){int n;scanf("%d", &n);priority_queue, greater> heap;while (n -- ){int x;scanf("%d", &x);heap.push(x);}int res = 0;while (heap.size() > 1){int a = heap.top(); heap.pop();int b = heap.top(); heap.pop();res += a + b;heap.push(a + b);}printf("%d\n", res);return 0;
}

#include 
#include 
using namespace std;
typedef long long LL;
const int N = 100010;
int n;
int t[N];
int main(){scanf("%d", &n);for (int i = 0; i < n; i ++ ) scanf("%d", &t[i]);sort(t, t + n);reverse(t, t + n);LL res = 0;for (int i = 0; i < n; i ++ ) res += t[i] * i;printf("%lld\n", res);return 0;
}

#include 
#include 
using namespace std;
const int N = 100010;
int n;
int q[N];
int main(){scanf("%d", &n);for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);sort(q, q + n);int res = 0;for (int i = 0; i < n; i ++ ) res += abs(q[i] - q[n / 2]);printf("%d\n", res);return 0;
}

#include 
#include 
using namespace std;
typedef pair PII;
const int N = 50010;
int n;
PII cow[N];
int main(){scanf("%d", &n);for (int i = 0; i < n; i ++ ){int s, w;scanf("%d%d", &w, &s);cow[i] = {w + s, w};}sort(cow, cow + n);int res = -2e9, sum = 0;for (int i = 0; i < n; i ++ ){int s = cow[i].first - cow[i].second, w = cow[i].second;res = max(res, sum - s);sum += w;}printf("%d\n", res);return 0;
}

#include 
#include 
using namespace std;
const int N = 100010;
int n, m;
int a[N], b[N];
int main(){scanf("%d%d", &n, &m);for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);int i = 0, j = 0;while (i < n && j < m){if (a[i] == b[j]) i ++ ;j ++ ;}if (i == n) puts("Yes");else puts("No");return 0;
}

#include 
#include 
#include 
#include 
#include 
using namespace std;
stack num;
stack op;
void eval(){auto b = num.top(); num.pop();auto a = num.top(); num.pop();auto c = op.top(); op.pop();int x;if (c == '+') x = a + b;else if (c == '-') x = a - b;else if (c == '*') x = a * b;else x = a / b;num.push(x);
}
int main(){unordered_map pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};string str;cin >> str;for (int i = 0; i < str.size(); i ++ ){auto c = str[i];if (isdigit(c)){int x = 0, j = i;while (j < str.size() && isdigit(str[j]))x = x * 10 + str[j ++ ] - '0';i = j - 1;num.push(x);}else if (c == '(') op.push(c);else if (c == ')'){while (op.top() != '(') eval();op.pop();}else{while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();op.push(c);}}while (op.size()) eval();cout << num.top() << endl;return 0;
}

#include 
#include 
#include 
#include 
using namespace std;
vector div(vector A, int b){vector C;for (int i = A.size() - 1, r = 0; i >= 0; i -- ){r = r * 10 + A[i];C.push_back(r / b);r %= b;}reverse(C.begin(), C.end());while (C.size() && C.back() == 0) C.pop_back();return C;
}
int main(){string s;while (cin >> s){vector A;for (int i = 0; i < s.size(); i ++ )A.push_back(s[s.size() - i - 1] - '0');string res;if (s == "0") res = "0";else{while (A.size()){res += to_string(A[0] % 2);A = div(A, 2);}}reverse(res.begin(), res.end());cout << res << endl;}return 0;
}

#include 
#include 
#include 
#include 
using namespace std;
int main(){int a, b;string s;cin >> a >> b >> s;vector A;for (int i = 0; i < s.size(); i ++ ){char c = s[s.size() - 1 - i];if (c >= 'A') A.push_back(c - 'A' + 10);else A.push_back(c - '0');}string res;if (s == "0") res = "0";else{while (A.size()){int r = 0;for (int i = A.size() - 1; i >= 0; i -- ){A[i] += r * a;r = A[i] % b;A[i] /= b;}while (A.size() && A.back() == 0) A.pop_back();if (r < 10) res += to_string(r);else res += r - 10 + 'a';}reverse(res.begin(), res.end());}cout << res << endl;return 0;
}

class Solution {
public:void rearrangedList(ListNode* head) {if (!head->next) return;int n = 0;for (auto p = head; p; p = p->next) n ++ ;int left = (n + 1) / 2;  // 前半段的节点数auto a = head;for (int i = 0; i < left - 1; i ++ ) a = a->next;auto b = a->next, c = b->next;a->next = b->next = NULL;while (c) {auto p = c->next;c->next = b;b = c, c = p;}for (auto p = head, q = b; q;) {auto o = q->next;q->next = p->next;p->next = q;p = p->next->next;q = o;}}
};

#include 
#include 
#include 
using namespace std;
const int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
};
int is_leap(int year){  // 闰年返回1，平年返回0if (year % 4 == 0 && year % 100 || year % 400 == 0)return 1;return 0;
}
int get_days(int y, int m){  // y年m月有多少天if (m == 2) return months[m] + is_leap(y);return months[m];
}
int main(){int y, s;while (cin >> y >> s){int m = 1, d = 1;s -- ;while (s -- ){if ( ++ d > get_days(y, m)){d = 1;if ( ++ m > 12){m = 1;y ++ ;}}}printf("%04d-%02d-%02d\n", y, m, d);}return 0;
}

#include 
#include 
#include 
using namespace std;
const int months[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
};
int is_leap(int year){if (year % 4 == 0 && year % 100 || year % 400 == 0)return 1;return 0;
}
int get_days(int y, int m){if (m == 2) return months[m] + is_leap(y);return months[m];
}
int get_year_days(int y, int m){if (m <= 2) return 365 + is_leap(y);return 365 + is_leap(y + 1);
}
int main(){int T;cin >> T;while (T -- ){int y, m, d, a;cin >> y >> m >> d >> a;if (m == 2 && d == 29) a --, m = 3, d = 1;while (a > get_year_days(y, m)){a -= get_year_days(y, m);y ++ ;}while (a -- ){if ( ++ d > get_days(y, m)){d = 1;if ( ++ m > 12){m = 1;y ++ ;}}}printf("%04d-%02d-%02d\n", y, m, d);}return 0;
}

class Solution {
public:int dfs(TreeNode* root, int depth) {if (!root) return 0;if (!root->left && !root->right) return root->val * depth;return dfs(root->left, depth + 1) + dfs(root->right, depth + 1);}int pathSum(TreeNode* root) {return dfs(root, 0);}
};

#include 
#include 
#include 
using namespace std;
const int INF = 1e8;
struct TreeNode{int val;TreeNode *left, *right;TreeNode(int _val): val(_val), left(NULL), right(NULL) {}
}*root;
void insert(TreeNode* &root, int x){if (!root) root = new TreeNode(x);else if (x < root->val) insert(root->left, x);else insert(root->right, x);
}
void remove(TreeNode* &root, int x){if (!root) return;if (x < root->val) remove(root->left, x);else if (x > root->val) remove(root->right, x);else{if (!root->left && !root->right) root = NULL;else if (!root->left) root = root->right;else if (!root->right) root = root->left;else{auto p = root->left;while (p->right) p = p->right;root->val = p->val;remove(root->left, p->val);}}
}
int get_pre(TreeNode* root, int x){if (!root) return -INF;if (root->val >= x) return get_pre(root->left, x);return max(root->val, get_pre(root->right, x));
}
int get_suc(TreeNode* root, int x){if (!root) return INF;if (root->val <= x) return get_suc(root->right, x);return min(root->val, get_suc(root->left, x));
}
int main(){int n;cin >> n;while (n -- ){int t, x;cin >> t >> x;if (t == 1) insert(root, x);else if (t == 2) remove(root, x);else if (t == 3) cout << get_pre(root, x) << endl;else cout << get_suc(root, x) << endl;}return 0;
}

class Solution {
public:string dfs(TreeNode* root) {if (!root) return "";if (!root->left && !root->right) return root->val;return '(' + dfs(root->left) + root->val + dfs(root->right) + ')';}string expressionTree(TreeNode* root) {return dfs(root->left) + root->val + dfs(root->right);}
};

class Solution {
public:int findMissMin(vector& nums) {int n = nums.size();vector hash(n + 1);for (int x: nums)if (x >= 1 && x <= n)hash[x] = true;for (int i = 1; i <= n; i ++ )if (!hash[i])return i;return n + 1;}
};

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int N = 100010;
int l, m, n;
int a[N], b[N], c[N];
int main(){scanf("%d%d%d", &l, &m, &n);for (int i = 0; i < l; i ++ ) scanf("%d", &a[i]);for (int i = 0; i < m; i ++ ) scanf("%d", &b[i]);for (int i = 0; i < n; i ++ ) scanf("%d", &c[i]);LL res = 1e18;for (int i = 0, j = 0, k = 0; i < l && j < m && k < n;){int x = a[i], y = b[j], z = c[k];res = min(res, (LL)max(max(x, y), z) - min(min(x, y), z));if (x <= y && x <= z) i ++ ;else if (y <= x && y <= z) j ++ ;else k ++ ;}printf("%lld\n", res * 2);return 0;
}

#include 
#include 
#include 
using namespace std;
int s[6][10];
int main(){int n, m;scanf("%d%d", &n, &m);while (n -- ){int x;scanf("%d", &x);for (int i = 0; i < m; i ++ ){s[i][x % 10] ++ ;x /= 10;}}for (int i = 0; i < m; i ++ ){int k = 0;for (int j = 0; j < 10; j ++ )if (s[i][k] < s[i][j])k = j;printf("%d\n", k);}return 0;
}

#include 
#include 
#include 
#include 
#include 
using namespace std;
int n;
int bfs(string start){queue q;unordered_map dist;dist[start] = 0;q.push(start);while (q.size()){auto t = q.front();q.pop();for (int i = 0; i < n; i ++ )if (t.substr(i, 4) == "2012")return dist[t];for (int i = 1; i < n; i ++ ){string r = t;swap(r[i], r[i - 1]);if (!dist.count(r)){dist[r] = dist[t] + 1;q.push(r);}}}return -1;
}
int main(){string start;cin >> n >> start;cout << bfs(start) << endl;return 0;
}

#include
using namespace std;
using pii = pair;
const int N = 1010;
int n, m, a[N][N], r[N][4], c[N][4];
queue q;
//给坐标[i, j]赋值为x
//同时判断第i 行是否有两个点，第j 列是否有两个点
void add(int i, int j, int x){a[i][j] = x;//如果第i 行一个点都没有，给定第一个点的值到r[i][0],列数为r[i][1]//其次如果第i 行没第二个点，给定第二个点的值到r[i][2],列数为r[i][3]，并且加入到bfs中//如果还有第三个点其实就不进行操作if(!r[i][0]) r[i][0] = x, r[i][1] = j;else if(!r[i][2]) r[i][2] = x, r[i][3] = j, q.push(i * 2 + 1);//如果是行扩展，加入奇数//对列进行同等操作if(!c[j][0]) c[j][0] = x, c[j][1] = i;else if(!c[j][2]) c[j][2] = x, c[j][3] = i, q.push(j * 2);//如果是列扩展，加入偶数
}
int main(){cin >> n >> m;for(int i = 0; i < n; i++)for(int j = 0; j < m; j++){int x;scanf("%d",&x);if(x) add(i, j, x);//给[i, j] 赋值 x}vector ans;//frist 里面存[x, y]坐标，sceond里面存值while(q.size()){int now = q.front() / 2, f = q.front() % 2; q.pop();//取出行号或者列号if(f){//如果是行扩展int suf = (r[now][2] - r[now][0]) / (r[now][3] - r[now][1]);//得到等差值int start = r[now][0] - (r[now][1] * suf);//求得第一个点的值for(int i = 0; i < m; i++){if(!a[now][i]){//如果a[now][i]是0，将a[now][i]按照等差公式赋值add(now, i, start + i * suf);//赋值ans.push_back({now * 2000 + i, start + i * suf});//加入[坐标，值]答案数组中}}}else{//列扩展，以下同理int suf = (c[now][2] - c[now][0]) / (c[now][3] - c[now][1]);int start = c[now][0] - (c[now][1] * suf);for(int i = 0; i < n; i++){if(!a[i][now]){add(i, now, start + i * suf);ans.push_back({i * 2000 + now, start + i * suf});}}}}sort(ans.begin(), ans.end());//按照坐标排序for(auto [xy, val] : ans){printf("%d %d %d\n",xy/2000+1,xy%2000+1,val);//输出答案}return 0;
}

#include 
#include 
#include 
#include 
using namespace std;
int n;
vector p;
vector g(int k){if (k == 1) return p;auto s = g(k - 1);int m = s.size();vector res(n * m);for (int i = 0; i < n * m; i ++ )res[i] = string(n * m, ' ');for (int i = 0; i < n; i ++ )for (int j = 0; j < n; j ++ )if (p[i][j] != ' ')for (int x = 0; x < m; x ++ )for (int y = 0; y < m; y ++ )res[i * m + x][j * m + y] = s[x][y];return res;
}
int main(){while (cin >> n, n){p.clear();getchar();  // 读掉n后的回车for (int i = 0; i < n; i ++ ){string line;getline(cin, line);p.push_back(line);}int k;cin >> k;auto res = g(k);for (auto& s: res) cout << s << endl;}return 0;
}

#include 
#include 
#include 
using namespace std;
const int N = 1000010, MOD = 1e9;
int n;
int f[N];
int main(){scanf("%d", &n);f[0] = 1;for (int i = 1; i <= n; i *= 2)for (int j = i; j <= n; j ++ )f[j] = (f[j] + f[j - i]) % MOD;cout << f[n] << endl;return 0;
}

#include 
#include 
#include 
using namespace std;
int main(){int a, b;while (cin >> a >> b){string x, y;for (int i = 15; i >= 0; i -- ){x += to_string(a >> i & 1);y += to_string(b >> i & 1);}y += y;if (y.find(x) != -1) puts("YES");else puts("NO");}return 0;
}

#include 
#include 
#include 
using namespace std;
const int N = 110, INF = 100000;
int n, m, k;
int s[N][N];
int main(){cin >> n >> m >> k;for (int i = 1; i <= n; i ++ )for (int j = 1; j <= m; j ++ ){cin >> s[i][j];s[i][j] += s[i - 1][j];}int res = INF;for (int x = 1; x <= n; x ++ )for (int y = x; y <= n; y ++ ){for (int i = 1, j = 1, sum = 0; i <= m; i ++ ){sum += s[y][i] - s[x - 1][i];while (sum - (s[y][j] - s[x - 1][j]) >= k){sum -= s[y][j] - s[x - 1][j];j ++ ;}if (sum >= k) res = min(res, (y - x + 1) * (i - j + 1));}}if (res == INF) res = -1;cout << res << endl;return 0;
}

#include 
#include 
#include 
using namespace std;
const int N = 15;
int n, m;
int w[N][N];
void mul(int c[][N], int a[][N], int b[][N]){static int tmp[N][N];memset(tmp, 0, sizeof tmp);for (int i = 0; i < n; i ++ )for (int j = 0; j < n; j ++ )for (int k = 0; k < n; k ++ )tmp[i][j] += a[i][k] * b[k][j];memcpy(c, tmp, sizeof tmp);
}
int main(){cin >> n >> m;for (int i = 0; i < n; i ++ )for (int j = 0; j < n; j ++ )cin >> w[i][j];int res[N][N] = {0};for (int i = 0; i < n; i ++ ) res[i][i] = 1;while (m -- ) mul(res, res, w);for (int i = 0; i < n; i ++ ){for (int j = 0; j < n; j ++ )cout << res[i][j] << ' ';cout << endl;}return 0;
}

#include 
#include 
#include 
using namespace std;
const int N = 5;
int n;
int g[N][N];
void rotate(int x, int y, int m){int w[N][N];memcpy(w, g, sizeof g);for (int i = 0; i < m; i ++ )for (int j = 0, k = m - 1; j < m; j ++, k -- )w[i][j] = g[x + k][y + i];for (int i = 0; i < m; i ++ )for (int j = 0; j < m; j ++ )g[x + i][y + j] = w[i][j];
}
int main(){for (int i = 0; i < 5; i ++ )for (int j = 0; j < 5; j ++ )cin >> g[i][j];int a, b, x, y;cin >> a >> b >> x >> y;x --, y -- ;if (a == 1) rotate(x, y, b);else{for (int i = 0; i < 3; i ++ )rotate(x, y, b);}for (int i = 0; i < 5; i ++ ){for (int j = 0; j < 5; j ++ )cout << g[i][j] << ' ';cout << endl;}return 0;
}

#include 
#include 
#include 
#include 
using namespace std;
const int N = 1000010;
int n;
char str[N];
int main(){scanf("%s", str + 1);unordered_map hash;n = strlen(str + 1);int res = 0;hash[0] = 0;for (int i = 1, s = 0; i <= n; i ++ ){if (str[i] == '0') s ++ ;else s -- ;if (hash.count(s)) res = max(res, i - hash[s]);else hash[s] = i;}printf("%d\n", res);return 0;
}

a = int(input())
b = int(input())
c = int(input())
d = int(input())
print("DIFERENCA = %d" % (a * b - c * d))

a, b = map(int, input().split(' '))
if a % b == 0 or b % a == 0:print("Sao Multiplos")
else:print("Nao sao Multiplos")

x, y = map(int, input().split(' '))
prices = [0, 4, 4.5, 5, 2, 1.5]
print("Total: R$ %.2lf" % (prices[x] * y))

print(len(input()))

while True:x = int(input())if x == 0:breakfor i in range(1, x + 1):print(i, end=' ')print()

import math
n = int(input())
for i in range(n):x = int(input())for j in range(2, int(math.sqrt(x)) + 1):if x % j == 0:print(x, "is not prime")breakelse:print(x, "is prime")

t = input()
s, c = 0, 0
for i in range(12):d = list(map(float, input().split(' ')))for j in range(12):if j > i:s += d[j]c += 1
if t == "M":s /= c
print("%.1f" % (s))

n, m = map(int, input().split())res = [[0 for j in range(m)] for i in range(n)]
dx, dy = [-1, 0, 1, 0], [0, 1, 0, -1]x, y, d = 0, 0, 1
for i in range(1, n * m + 1):res[x][y] = ia, b = x + dx[d], y + dy[d]if a < 0 or a >= n or b < 0 or b >= m or res[a][b]:d = (d + 1) % 4a, b = x + dx[d], y + dy[d]x, y = a, bfor i in range(n):for j in range(m):print(res[i][j], end = ' ')print()

n = int(input())
path = [0 for i in range(n)]
used = [False for i in range(n)]def dfs(u):if u == n:for i in range(n):print(path[i] + 1, end=' ')print()else:for i in range(n):if not used[i]:path[u] = iused[i] = Truedfs(u + 1)used[i] = Falsepath[u] = 0dfs(0)

#输入无行数限制
while True:try:a, b = map(int, input().split())print(a + b)except:break

#先输入行数
n = int(input())
while n:a, b = map(int, input().split())print(a + b)n -= 1

#输入00结束
while True:a, b = map(int, input().split())if a != 0 and b != 0: print(a + b)else: break

#给定数组长度,输入0停止
while True:arr = list(map(int, input().split()))if arr[0] == 0: breakelse: print(sum(arr[1:]))

#给定总数组数量
n = int(input())
while n:print(sum(list(map(int, input().split()))[1:]))n -= 1

#不给定总数组数量
while True:try:  # 对于没有行提示的，使用try except就很简单print(sum(list(map(int, input().split()))[1:]))except:break

# 不给行数和每行数组长度
while True:try:print(sum(list(map(int, input().split()))))except:break

#给定字符数量
n = int(input())
arr = input().split()
arr.sort()
print(' '.join(arr))

#不给定字符数量
while True:try:arr = input().split()arr.sort()print(" ".join(arr))except:break

#逗号分割
while True:try:arr = input().split(",")arr.sort()print(",".join(arr))except:break