自用结论 + 板子

摘要
Title: 自用结论 + 板子
Memory Limit: 64 MB
Time Limit: 1000 ms

结论

只要一个字符串中的任何字符，都不与它前两个字符相同，这个字符串就不包含任何长度为 2 或者更长的回文字符串。
- 习惯性的推结论，先推状态为1,2的
遇到奇偶个数校验，想到：XOR（将奇偶型转换为01问题，奇变偶，偶变奇，就是将当前状态异或1即可）
遇到有限的参数（小于20个）表状态，想到：状态压缩
遇到求最长的连续子串使得和为k，想到：前缀和 + 哈希表记录第一次出现某一状态的位置
1 + sum((x & 1) ^ (y & 1) for x, y in pairwise(nums)) 等价于 奇偶交替的最长子序列长度
在dfs中，用了for循环加入未被选的元素，实际上更改了相对位置，其实就相当于把顺序也考虑上了，相当于排列，而不是组合
对于一个有序数列X, 找一个点p，使得 $\sum^{n}_{i=1} abs(p-x_i)$ 的和最小，这个点就是数列的中位数（货仓选址问题）
单调性结论 (这样就可以支持二分+st)
- 按位与操作结果的单调性是非递增的。
- gcd操作结果的单调性是非递增的。
- 按位或操作结果的单调性是非递减的。
- lcm操作结果的单调性是非递减的。
- 数组求和操作结果的单调性是单调递增的。
- 数组最大值操作结果的单调性是单调递增的。
- 数组最小值操作结果的单调性是单调递减的。
- 对于有两个变量的题目，通常可以枚举其中一个变量，把它视作常量，从而转化成只有一个变量的问题。(枚举右，维护左)
二进制与集合：https://leetcode.cn/circle/discuss/CaOJ45/
- 当遇到二进制计算的dp问题时，可以想到用位运算优化
对于两个点 $(x_1, y_1)$ 和 $(x_2, y_2)$ ，计算新坐标 $A$ 和 $B$ 后，曼哈顿距离等于这两个新坐标差值的最大值：
$d_M((x_1, y_1), (x_2, y_2)) = d_C((A_1, B_1), (A_2, B_2)) = \max(|A_1 - A_2|, |B_1 - B_2|)$
https://oi-wiki.org/geometry/distance/
当其中一个数组元素各不相同时，最长公共子序列问题（LCS）可以转换为最长上升子序列问题（LIS）进行求解。同时最长上升子序列问题（LIS）存在使用「维护单调序列 + 二分」的贪心解法，复杂度为 O(nlogn)，当然也可以采取树状数组或者线段树进行优化
子数组中任意两个数按位与均为 0，意味着任意两个数对应的集合的交集为空 (https://leetcode.cn/circle/discuss/CaOJ45/)

模运算

(a+b)%mod=k⟹(a%mod+b%mod)%mod=k
(a×b)%mod=k⟹((a%mod)×(b%mod))%mod=k
(a−b)%mod=k⟹(b%mod+k)%mod=a%mod
(a×b^(−1))%mod=k⟹(a%mod×b^(-1)%mod)%mod=k
(a/b)%mod=k⟹(a%mod×b^(mod−2))%mod=k

对某个数据对象用max和min函数时，要注意是否非空！！！
记忆化搜索可用 @lru_cache，到最后的时候记得 dfs.cache_clear() # 防止爆内存
当出现两个线段，两个点，怎么怎么样的时候，想到
- 前后缀分解
- 枚举右，维护左（利用二分或滑动窗口求解）

板子

# 3.8.19 import
import random
from collections import Counter, defaultdict, deque
from datetime import datetime, timedelta
from functools import lru_cache
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from itertools import combinations, compress, permutations, starmap, tee
from math import ceil, fabs, floor, gcd, log, sqrt
from string import ascii_lowercase, ascii_uppercase
from sys import exit, setrecursionlimit, stdin
from typing import Any, Dict, List, Tuple, TypeVar, Union

# Constants
TYPE = TypeVar('TYPE')
N = int(2e5 + 10)
M = int(20)
INF = int(1e12)
OFFSET = int(100)
MOD = int(1e9 + 7)

# Set recursion limit
setrecursionlimit(int(2e9))


class Arr:
    array = staticmethod(lambda x=0, size=N: [x() if callable(x) else x for _ in range(size)])
    array2d = staticmethod(lambda x=0, rows=N, cols=M: [Arr.array(x, cols) for _ in range(rows)])
    graph = staticmethod(lambda size=N: [[] for _ in range(size)])


class Math:
    max = staticmethod(lambda a, b: a if a > b else b)
    min = staticmethod(lambda a, b: a if a < b else b)


class IO:
    input = staticmethod(lambda: stdin.readline().rstrip("\r\n"))
    read = staticmethod(lambda: map(int, IO.input().split()))
    read_list = staticmethod(lambda: list(IO.read()))


class Std:
    pass

# ————————————————————— Division line ——————————————————————