小明の雜貨鋪

char ascii 0 48 9 57 A 65 Z 90 a 97 z 122 经典字典树 主机场 给定一组字符串 s1,s2,⋯ ,sns_1,s_2,\cdots,s_ns1​,s2​,⋯,sn​，任选 kkk 个 sa1,sa2,⋯ ,sak (ai≠aj)s_{a_1},s_{a_2},\cdots,s_{a_k}\ (a_{i}\ne a_{j})sa1​​,sa2​​,⋯,sak​​ (ai​=aj​)，最小化 max⁡1⩽i,j⩽k,i≠jlcp⁡(sai,saj)\max\limits_{1 \leqslant i,j \leqslant k,i\ne j}^{}\operatorname{lcp}(s_{a_i},s_{a_j})1⩽i,j⩽k,i=jmax​lcp(sai​​,saj​​)。其中 lcp⁡(p,q)\operatorname{lcp}(p,q)lcp(p,q) 是字符串 ppp 和字符串 qqq...

Brute Force CF1997E. Level Up Monocarp 正在玩一款电脑游戏。他从等级 111 开始。他将依次与 nnn 只怪物战斗，这些怪物的等级从 111 到 nnn 不等。 对于按顺序给出的每个怪物，Monocarp 的遭遇如下： 如果 Monocarp 的等级高于怪物的等级，则怪物会逃跑； 否则，Monocarp 会与怪物战斗。 在每与第 kkk 个怪物战斗（逃跑的怪物不计算在内）后，Monocarp 的等级会增加 111 。因此，他在与 kkk 个怪物战斗后等级变为 222 ，在与 2k2k2k 个怪物战斗后等级变为 333 ，以此类推。 你需要处理 qqq 个查询，每个查询的格式如下： i xi~xi x ：如果参数 kkk 等于 xxx ，Monocarp 是否会与第 iii 个怪物战斗？ 方法一 首先离线询问。 无论用什么方法，k=1k=1k=1 时总是退化为暴力，因此考虑根号分治，当 k<nk<\sqrt{n}k<n​ 时暴力。这部分的复杂度 Θ(nn)\Theta(n\sqrt{...

后缀数组 后缀数组 (Suffix Array, SA) 是把字符串的所有 后缀 按 字典序 排序后得到的数组。 定义： 排名数组 rk⁡w(i)\operatorname{rk}_w(i)rkw​(i)：从第 iii 位开始、长度为 www 的子串在所有长度为 www 的子串中的排名； 编号数组 sa⁡w(i)\operatorname{sa}_w(i)saw​(i)：长度为 www 的子串中字典序第 iii 小的一个的开始位置，与排名数组互逆，即 sa⁡(rk⁡(i))=i\operatorname{sa}(\operatorname{rk}(i))=isa(rk(i))=i，rk⁡(sa⁡(i))=i\operatorname{rk}(\operatorname{sa}(i))=irk(sa(i))=i。 用倍增法在 Θ(nlog⁡n)\Theta(n\log n)Θ(nlogn)...

斐波那契数列的 20 种求法 矩阵快速幂 题意 设 an={an−1+an−2,n⩾31,n=1∨n=2a_{n}=\begin{cases}a_{n-1}+a_{n-2},&n \geqslant 3\\1,&n=1\lor n=2\end{cases}an​={an−1​+an−2​,1,​n⩾3n=1∨n=2​，求 an mod ma_n\bmod man​modm。 解 设 M=[0111]\mathbf{M}=\begin{bmatrix}0 &1\\ 1 & 1\end{bmatrix}M=[01​11​]​，则 [Fn0Fn+10]=Mn−1[1010]\begin{bmatrix}F_n & 0 \\ F_{n+1} & 0\end{bmatrix} =\mathbf{M}^{n-1}\begin{bmatrix}1 & 0 \\ 1 & 0 \end{bmatrix} [Fn​Fn+1​​00​]=Mn−1[11​00​] 于是...

Manacher Algorithm Find the longest substring which is palindrome. 在搜索到 iii 时， cc,ll,rr 已经找到的右边界最大的回文串的中心、左端和右端。 p[i] 以 iii 为中心的最长回文串长度。如果 iii 在最长回文串之中，p[i] 至少是它对称位置的 p[mirror]。利用此性质快速计算 p[i]。 123456789101112131415161718vector<int> manacher(const string& s) { string t = "#"; for (auto c : s) t += c, t += '#'; const int n = t.size(); vector<int> r(n);  // 存储每个字符作为中心的最长回文子串的半径 for (int i = 0, j = 0; i < n; i++) { if (2...

裂项 ∑i=1n(ai−ai+k)=∑i=1kai−∑i=n+1n+kai\sum_{i=1}^{n}(a_{i}-a_{i+k})=\sum_{i=1}^{k}a_{i}-\sum_{i=n+1}^{n+k}a_{i} i=1∑n​(ai​−ai+k​)=i=1∑k​ai​−i=n+1∑n+k​ai​ 约瑟夫环问题 约瑟夫环问题 设 Jn,mJ_{n, m}Jn,m​ 表示规模分别为 n,mn, mn,m 的约瑟夫问题的答案。我们有如下递归式 Jn,m=(Jn−1,m+m) mod nJ_{n, m}=\left(J_{n-1, m}+m\right) \bmod n Jn,m​=(Jn−1,m​+m)modn 这个也很好推。从 0 开始数 mmm 个，让第 m−1m-1m−1 个人出局后剩下 n−1n-1n−1 个人，计算出在 n−1n-1n−1 个人中选的答案后，再加一个相对位移 mmm 得到真正的答案。 题目说是从 kkk 开始报数，所以答案再加上 kkk。 时间复杂度 Θ(n)\Theta(n)Θ(n)： 12345int res = 0;for (int i =...

博弈论 是经济学的一个分支； 主要研究具有竞争或对抗性质的对象在一定规则下的行为； 考虑个体中的预测行为和实际行为，并研究其优化策略； 通俗地讲，主要研究的是在一个游戏中进行游戏的多位玩家的策略。 公平组合游戏（ICG） 二人参与，轮流决策，每次可以在有限的合法决策集合中选择一种进行操作，双方均知道游戏的完整信息； 在某一确定状态做出的决策集合只与状态有关，与玩家、之前的操作等任何因素都无关； 如果轮到某位玩家的回合时合法决策集合为空（即无法进行操作），该名玩家负。游戏一定会在有限步数之后以非平局结束； 大部分棋类游戏都是非公平组合游戏：国际象棋，五子棋等，因为双方都无法使用对方的棋子。 博弈图 给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。 任何一个 ICG 游戏都可以转化为有向图游戏：把每个状态视为一个节点，向它的后继状态连边，转化为有向图游戏，也称绘制了它的博弈状态图（简称博弈图或者游戏图）。 ...

逆元 模为素数 123456789101112131415constexpr int mod = 998244353;ll qpow(ll a, ll n) { ll res = 1; while (n) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res;}int inv(int n) { return qpow(n, mod - 2);} // 1/a (p 是素数) 非固定模数 123456789101112131415161718192021222324252627282930ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a;}ll exgcd(ll a, ll b, ll& x, ll& y) { if (b ==...

2024 牛客多校 9I - Interesting Numbers [[…/contests/2024 牛客多校 /2024-08-13：2024 牛客暑期多校训练营 9|2024-08-13：2024 牛客暑期多校训练营 9]] 1234567891011121314151617181920import mathn = int(input())l, r = map(int, input().split())def slove(k) : wei = 10 ** (n // 2) half1 = k // wei half2 = k % wei half3 = 10 ** (n // 2) sqr1 = math.isqrt(half1) sqr2 = math.isqrt(half2) sqr3 = math.isqrt(half3) if sqr3 * sqr3 == half3: sqr3 -= 1 if half1 == sqr1 ** 2: return sqr1 *...

平面计算几何 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899using T = double;const double eps = 1e-9, pi = acos(-1.0);int sgn(T x) { return (fabs(x) <= eps) ? 0 : (x < 0 ? -1 : 1);}struct P { T x, y; P() : x(0), y(0) {} P(T x, T y) : x(x), y(y) {} // P(T r, double alpha, int _) : x(r * cos(alpha)), y(r *...