package copypasta

import (

"bytes"

"math"

"regexp"

"slices"

"sort"

"strconv"

"strings"

)

/* 其他无法分类的算法 ad-hoc

- [764. 最大加号标志](https://leetcode.cn/problems/largest-plus-sign/) 1753

最大子矩形 https://www.luogu.com.cn/problem/P1578

倒数平方根 https://www.bilibili.com/video/BV17N41167dR/

小奥

https://codeforces.com/problemset/problem/700/A

原地哈希

LC442 https://leetcode.cn/problems/find-all-duplicates-in-an-array/

三维 n 皇后 https://oeis.org/A068940

Maximal number of chess queens that can be placed on a 3-dimensional chessboard of order n so that no two queens attack each other

Smallest positive integer k such that n = +-1+-2+-...+-k for some choice of +'s and -'s https://oeis.org/A140358

https://codeforces.com/problemset/problem/11/B

https://codeforces.com/problemset/problem/1278/B

LC754 https://leetcode.cn/problems/reach-a-number/ 1880

Numbers n such that n is the substring identical to the least significant bits of its base 2 representation.

https://oeis.org/A181891

https://oeis.org/A181929 前缀

https://oeis.org/A038102 子串

Maximal number of regions obtained by joining n points around a circle by straight lines.

Also number of regions in 4-space formed by n-1 hyperplanes.

a(n) = n*(n-1)*(n*n-5*n+18)/24+1 https://oeis.org/A000127

https://oeis.org/A001069 Log2*(n) (version 2): take log_2 of n this many times to get a number < 2

https://oeis.org/A211667 Number of iterations sqrt(sqrt(sqrt(...(n)...))) such that the result is < 2

a(n) = 1, 2, 3, 4, 5, ... for n = 2^1, 2^2, 2^4, 2^8, 2^16, ..., i.e., n = 2, 4, 16, 256, 65536, ... = https://oeis.org/A001146

https://oeis.org/A002024 n appears n times; a(n) = floor(sqrt(2n) + 1/2) https://www.zhihu.com/question/25045244

找规律 https://codeforces.com/problemset/problem/1034/B

长度为 n 的所有二进制串，最多能划分出的 11 的个数之和 https://oeis.org/A045883

相关题目 https://codeforces.com/contest/1511/problem/E

https://oeis.org/A007302 Optimal cost function between two processors at distance n

bits.OnesCount(3*n ^ n)

LC2571 https://leetcode.cn/problems/minimum-operations-to-reduce-an-integer-to-0/

解释 https://leetcode.cn/problems/minimum-operations-to-reduce-an-integer-to-0/solution/ji-yi-hua-sou-suo-by-endlesscheng-cm6l/

4 汉诺塔 https://oeis.org/A007664

Reve's puzzle: number of moves needed to solve the Towers of Hanoi puzzle with 4 pegs and n disks, according to the Frame-Stewart algorithm

https://www.acwing.com/problem/content/description/98/

麻将

2021·昆明 https://ac.nowcoder.com/acm/contest/12548/K

五子棋

https://codeforces.com/contest/825/problem/B

调度场算法 shunting-yard algorithm

中缀转后缀

https://en.wikipedia.org/wiki/Shunting-yard_algorithm

*/

func miscCollection() {

}

// b 是 a 的一个排列（允许有重复元素）

// 返回 b 中各个元素在 a 中的下标（重复的元素顺序保持一致）

// 可用于求从 a 变到 b 需要的相邻位元素交换的最小次数，即返回结果的逆序对个数

// LC1850 https://leetcode.cn/problems/minimum-adjacent-swaps-to-reach-the-kth-smallest-number/

func mapPos(a, b []int) []int {

}

/* 归并排序与逆序对

- 归并排序：[912. 排序数组](https://leetcode.cn/problems/sort-an-array/)

- [LCR 170. 交易逆序对的总数](https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/)

- [327. 区间和的个数](https://leetcode.cn/problems/count-of-smaller-numbers-after-self/)

- [327. 区间和的个数](https://leetcode.cn/problems/count-of-range-sum/)

- [493. 翻转对](https://leetcode.cn/problems/reverse-pairs/)

一张关于归并排序的好图 https://www.cnblogs.com/chengxiao/p/6194356.html

*/

func mergeCount(a []int) int {

}

// 状压 N 皇后

// https://oeis.org/A000170 Number of ways of placing n non-attacking queens on an n X n board

// Strong conjecture: there is a constant c around 2.54 such that a(n) is asymptotic to n!/c^n

// Weak conjecture: lim_{n -> infinity} (1/n) * log(n!/a(n)) = constant = 0.90....

// https://arxiv.org/pdf/2107.13460.pdf

// LC51 https://leetcode.cn/problems/n-queens/

// LC52 https://leetcode.cn/problems/n-queens-ii/

func totalNQueens(n int) (ans int) {

}

// 格雷码 https://oeis.org/A003188 https://oeis.org/A014550

// https://en.wikipedia.org/wiki/Gray_code

// LC89 https://leetcode.cn/problems/gray-code/

// 转换 https://codeforces.com/problemset/problem/1419/E

func grayCode(length int) []int {

}

// 输入两个无重复元素的序列，返回通过交换相邻元素，从 a 到 b 所需的最小交换次数

// 保证 a b 包含相同的元素

func countSwap(a, b []int) int {

}

// 输入一个仅包含 () 的括号串，返回右括号个数不少于左括号个数的非空子串个数

func countValidSubstring(s string) (ans int) {

}

// 负二进制数相加

// LC1073 https://leetcode.cn/problems/adding-two-negabinary-numbers/

func addNegabinary(a1, a2 []int) []int {

}

// 负二进制转换

// https://atcoder.jp/contests/abc105/tasks/abc105_c

// LC1017 https://leetcode.cn/problems/convert-to-base-2/

func toNegabinary(n int) (ans string) {

}

// 分数转小数

// https://en.wikipedia.org/wiki/Repeating_decimal

// Number of digits in decimal expansion of 1/n before the periodic part begins https://oeis.org/A051628

// - 设 n=2^c2*5^c5*...，那么 A051628(n) = max(c2,c5)

// Period of decimal representation of 1/n, or 0 if 1/n terminates https://oeis.org/A051626

// - 如果 n 的质因子只有 2 和 5，那么不存在循环节

// - 否则，先把 n 移除所有质因子 2 和 5，得到 m，那么 A051626(n) = n_order(10, m) 请看 math.go 中的「阶」

// - 参考 https://zhuanlan.zhihu.com/p/346536813 https://www.zhihu.com/question/462266812

// The periodic part of the decimal expansion of 1/n https://oeis.org/A036275

// 例如 (2, -3) => ("-0.", "6")

// b must not be zero

//

// https://oeis.org/A007732 Period of decimal representation of 1/n

// https://oeis.org/A084680 Order of 10 modulo n [i.e., least m such that 10^m = 1 (mod n)] or 0 when no such number exists

// https://oeis.org/A002329 Periods of reciprocals of integers prime to 10

//

// LC166 https://leetcode.cn/problems/fraction-to-recurring-decimal/

// WF1990 https://www.luogu.com.cn/problem/UVA202

// 1e12 加强版 https://ac.nowcoder.com/acm/contest/62622/E

// Python 代码 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=63288994

// b 进制下是否为有限小数 https://codeforces.com/problemset/problem/983/A 1700

func fractionToDecimal(a, b int) (beforeCycle, cycle []byte) {

}

// 小数转分数

// decimal like "2.15(376)", which means "2.15376376376..."

// https://zh.wikipedia.org/wiki/%E5%BE%AA%E7%8E%AF%E5%B0%8F%E6%95%B0#%E5%8C%96%E7%82%BA%E5%88%86%E6%95%B8%E7%9A%84%E6%96%B9%E6%B3%95

func decimalToFraction(decimal string) (a, b int) {

}

// 表达式计算（无括号）

// LC227 https://leetcode.cn/problems/basic-calculator-ii/

func calculate(s string) (ans int) {

}

// 倒序思想

// 来源自被删除的 C 题 https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45798625

// 有一个大小为 n*m 的网格图，和一个长为 n*m 的目标位置列表，每个位置表示网格图中的一个格点且互不相同

// 网格图初始为空

// 按照此列表的顺序，一个士兵从网格图边缘的任意位置进入并到达目标位置，到达后该士兵停留在此格点，下一个士兵开始进入网格图

// 每个士兵会尽可能地避免经过有士兵的格点

// 输出每个士兵必须经过的士兵数之和

// n, m <= 500

// 思路：

// 将问题转化成从最后一个士兵开始倒着退出网格

// 对于一个填满的网格图，每个士兵到边缘的最短路径就是离他最近的边缘的距离

// 当一个士兵退出网格后，BFS 地更新他周围的士兵到边缘的最短路径（空格点为 0，有人的格点为 1）

// 复杂度 O((n+m)*min(n,m)^2)

func minMustPassSum(n, m int, targetCells [][2]int) int {

}

// 马走日从 (0,0) 到 (x,y) 所需最小步数

// 无边界 LC1197 https://leetcode.cn/problems/minimum-knight-moves/

// 有边界+打印方案 https://www.acwing.com/problem/content/3527/

func minKnightMoves(x, y int, abs func(int) int) int {

}

// 网格图

// 从 (sx,sy) 出发，向右下走，遇到边界反弹，返回到达 (tx,ty) 的最小步数

// 若无法到达，返回 -1

func minDiagonalMove(n, m, sx, sy, tx, ty int) (step int) {

}

// 判断 6 个矩形是否为长方体的 6 个面

// NEERC04 https://www.luogu.com.cn/problem/UVA1587

func isCuboid(rect [][2]int) bool {

}

// 约瑟夫问题

// 思路：用递推公式，自底向上计算

// https://zh.wikipedia.org/wiki/%E7%BA%A6%E7%91%9F%E5%A4%AB%E6%96%AF%E9%97%AE%E9%A2%98

// https://oi-wiki.org/misc/josephus/ 注意当 k 较小时，存在 O(klogn) 的做法

// https://www.scirp.org/pdf/OJDM_2019101516120841.pdf Generalizations of the Feline and Texas Chainsaw Josephus Problems

//

// LCR187 https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/

// LC1823 https://leetcode.cn/problems/find-the-winner-of-the-circular-game/

// https://codeforces.com/gym/101955/problem/K

func josephusProblem(n, k int) int {

}

// 均分纸牌 https://www.luogu.com.cn/problem/P1031

// 环形 https://www.luogu.com.cn/problem/P2512 https://www.luogu.com.cn/problem/P3051 https://www.luogu.com.cn/problem/P4016 UVa11300 https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=25&page=show_problem&problem=2275

// 环形+打印方案 https://www.luogu.com.cn/problem/P2125

// 二维环形 https://www.acwing.com/problem/content/107/

func minMoveToAllSameInCircle(a []int, abs func(int) int) (ans int) {

}

// 表达式转表达式树

// https://leetcode.cn/submissions/detail/186220993/

func parseExpression(s string) {

}

// 钱珀瑙恩数 Champernowne constant

// https://en.wikipedia.org/wiki/Champernowne_constant

// https://oeis.org/A033307

// 返回第 k 位数字

// https://leetcode.cn/contest/espressif-2021/problems/fSghVj/

func champernowneConstant(k int) int {

}

// 摩尔投票法求绝对众数（absolute mode, majority）

// Boyer–Moore majority vote algorithm

// https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_majority_vote_algorithm

// LC169 https://leetcode.cn/problems/majority-element/

// LC229 变形 https://leetcode.cn/problems/majority-element-ii/

// LC2780 https://leetcode.cn/problems/minimum-index-of-a-valid-split/

func majorityVote(a []int) (mode int) {

}

// 给出二维平面上的 n 个坐标点，以 (x,y) 为中心的十字最多能覆盖多少个点？

// https://atcoder.jp/contests/abc176/tasks/abc176_e

// 进阶：每个点有不同的点权 https://atcoder.jp/contests/abc298/tasks/abc298_f

func maxCover(a [][3]int) (ans int) {

}

// 至多 k 次操作，每次操作把一个数减一，目标是最小化数组最大值

// 不能把 a[i] 改成负数

// https://codeforces.com/problemset/problem/960/B

func minMaxArray(a []int, k int) {

}

// 将 "aa...abb...b" (a 个 'a' 和 b 个 'b') 中的 b 向左移动 k 次，得到的字典序最大的字符串是什么？

func moveAB(a, b, k int) string {