【算法介绍】分块思想
算法简介：舍径求真分块思想，是一种把数据分为若干个块，以比正解略劣的复杂度通过题目的思想。适用于一些树形结构可以处理的区间类问题，比如说线段树之类的，分块可以做到基本平替。分块思想主要分为两个部分，完整块和边角块。对于查询的区间，肯定会有边角的至多两个块是不完整的，而不完整的块我们可以尝试暴力，完整的块我们也可以一块一块的数。这样几乎完全暴力的做法，就是分块的优势。
算法试用：忘形炼智算法推导：漫行灵圃那么继续上面的简介内容，我们不难想到，想要让边角小块的暴力与内部整块的枚举达到某种平衡，最为方便的，就是把每个块的大小设为 $\sqrt n$ 。这样就可以保证块的大小以及块的数量都是 $\sqrt n$ ，总体的复杂度自然也是 $O(n\sqrt n)$ 。
那么口说无凭，我们就以动态区间和这道线段树或者树状数组的模板题举例。
首先给出一个序列 $a$ 表示被操作的数组。数组长度为 11 。
a = \big[1,2,-3,4,8,9,-2,3,0,-1,5\big]那么按照上面说的取根号作为块的大小，我们会得到下面的分块情况。每一个下标对应块的起始位置和终止位置一般是 $\left ...
【拾题杂谈】关于一道博弈类双变量贪心题及其思考
题面小A和小B又在通过游戏决一胜负了。
今天他们玩的游戏是这样的，小A拿出了张卡片，每张卡片上都写了一个数 $a$ 。他们每个人轮流交替取走一张卡片，直到取完，小A先取。
记小A取走的卡片的权值和为 $A$ ，小B取走的卡片的权值和为 $B$ ，则小A最终得分为 $|A|-|B|$ 。小A自然希望自己的得分最大，小B则希望其得分最小。
优策略的情况下，小A的最终得分是多少？
$n\le 1e5$
思路不难发现，这就是一道非常经典的博弈类型的贪心题。这里有两个人，小A和小B，他们分别有着自己的决策 $A,B$ ，得分的表现形式为 $|A|-|B|$ ，所以说这是一道双变量的博弈。而处理这种问题的方法之一，就是把双变量转化为单变量。而想要把双变量转化为单变量，我们需要找到不变量。
观察题目，不难发现不变量就是所有元素之和。我们记 $sum = \sum\limits_{i=1}^n a_i$ 。那么当小A取得行动得分 $|A|$ 时，小B的分数自然是 $|sum-A|$ 。最后的答案就等价于 $|A|-|sum-A|$ 。如果我们用函数 $f(A)$ 表示结果，我们可以得到函数 $f(A) ...
【奇技淫巧】和式交换
概念：和式交换所谓和式交换的概念，大家一定都不陌生。小学就学过加法交换律，带符号搬家之说。和式交换就是基于这样的一个原理进行的一个数学技巧。
使用：数学及动规其实数学上的做法大家一定都不陌生，再动态规划上，我们可以使用和式交换的方式优化复杂度。其表现大概为，把一种递推的分组替换为另一种较少的分组用一些和形式的优化使得复杂度降低。
这里以一道题目来看看他的具体用法。
例题：魔法门*来源 MX
给出一个 $n$ 个点，每个点有一个点权 $a_i$ 。任意两个点 $i,j$（ $i<j$ ）之间存在魔法门共 $f(a_i \& a_j)$ 个，$f(x)$ 表示数字 $x$ 在二进制下 $1$ 的数量，$\&$ 表示按位与操作。问从 $1$ 到 $n$ 的方案数量，答案对 $998244353$ 取模。
这个题目首先一定会做的是 $O(n^2)$ 的算法。我们可以设置起点为 $i$ 终点为 $j$ ，写出状态 $dp[i]$ 表示从 $1$ 到 $i$ 的方案数。写出如下代码：
12345for(int i = 1; i <= n; i++) { ...
【拾题杂谈】LuoguP6329 震波
题面大秦为你打开题目传送门
题目背景模板题，没有 $rap$ 。
题目描述在一片土地上有 $n$ 个城市，通过 $n-1$ 条无向边互相连接，形成一棵树的结构，相邻两个城市的距离为 $1$，其中第 $i$ 个城市的价值为 $value_i$。
不幸的是，这片土地常常发生地震，并且随着时代的发展，城市的价值也往往会发生变动。
接下来你需要在线处理 $m$ 次操作：
0 x k 表示发生了一次地震，震中城市为 $x$，影响范围为 $k$，所有与 $x$ 距离不超过 $k$ 的城市都将受到影响，该次地震造成的经济损失为所有受影响城市的价值和。
1 x y 表示第 $x$ 个城市的价值变成了 $y$ 。
为了体现程序的在线性，操作中的 $x$、$y$、$k$ 都需要异或你程序上一次的输出来解密，如果之前没有输出，则默认上一次的输出为 $0$ 。
输入格式第一行包含两个正整数 $n$ 和 $m$ 。
第二行包含 $n$ 个正整数，第 $i$ 个数表示 $value_i$ 。
接下来 $n-1$ 行，每行包含两个正整数 $u$、$v$，表示 $u$ 和 $v$ 之间有一条无向边。
接下来 $m$ ...
【算法介绍】点分治算法
算法简介：理清逃跑路线点分治是一种处理树上任意点对路径的算法，他可以更据每一个路径的组成部分进行分治。对于我们选出树上上的点 $\tt root$ 作为根，一条路径可以分为：
与根无关
端点为根
经过根
根据这些信息，我们可以用分治的思想处理这样的数据。
算法演示：都交给分身吧算法推导：快是第一奥义首先按照上面所说我们把一个路径分为了与根无关、端点为根、经过根这三种情况。不难直接想到可以用分治解决。因为与根无关，我们就去找子树，经过根我们就用两个端点为根的拼起来。
那么为了保证复杂度，我们最优的选择一定是以重心作为根。这样的话只会选择 log 次。
举个例子，我们要求一棵树上有没有距离为 k 的点对，我们对于选出来的根，枚举其所有的儿子，求出他的子树里面所有点对于他的距离，然后我们就看别的子树里面有没有距离和他能凑成 k 的就可以。
值得注意的是，在这种算法里，最好都不要使用 memset 这会导致复杂度不正确。
代码也好写：
123456789101112131415161718192021222324252627282930313233343536373839404142434 ...
【拾题杂谈】LuoguP5024 保卫王国
题面大秦为你打开题目传送门
题目描述Z 国有 $n$ 座城市，$(n - 1)$ 条双向道路，每条双向道路连接两座城市，且任意两座城市都能通过若干条道路相互到达。
Z 国的国防部长小 Z 要在城市中驻扎军队。驻扎军队需要满足如下几个条件：
一座城市可以驻扎一支军队，也可以不驻扎军队。
由道路直接连接的两座城市中至少要有一座城市驻扎军队。
在城市里驻扎军队会产生花费，在编号为 $i$ 的城市中驻扎军队的花费是 $p_i$。
小 Z 很快就规划出了一种驻扎军队的方案，使总花费最小。但是国王又给小 Z 提出了 $m$ 个要求，每个要求规定了其中两座城市是否驻扎军队。小 Z 需要针对每个要求逐一给出回答。具体而言，如果国王提出的第 $j$ 个要求能够满足上述驻扎条件（不需要考虑第 $j$ 个要求之外的其它要求），则需要给出在此要求前提下驻扎军队的最小开销。如果国王提出的第 $j$ 个要求无法满足，则需要输出 $-1$。现在请你来帮助小 Z。
输入格式第一行有两个整数和一个字符串，依次表示城市数 $n$，要求数 $m$ 和数据类型 $type$。$type$ ...
【算法介绍】高斯消元
算法简介：九鹦之喙高斯消元是一种快速求一些线性方程组的算法。消元法是一种用某一种未知数表示另外一种未知数从而减少未知数数量得到解的方法。而众所周知，消元法的理论基础是等式的性质。
算法演示：星虎之掌算法推导：蜂鸟之羽首先给出一个简单的三元一次方程组：
\begin{cases}
3x + 2y + z = 10\\
5x + y + 6z = 25\\
2x + 3y + 4z = 20
\end{cases}初中学过的消元方式就是加减消元、代入消元。解这个方程的话，首先用第二个式子变形分别消掉一三式子里面的 $x$ ，这是候一三方程式就构成了一个二元一次方程组，解出来了就全解出来了。
我们可以用一种矩阵的形式去表示整个方程组：
\left[\
\begin{matrix}
3&2&1&|&10\\
5&1&6&|&25\\
2&3&4&|&20
\end{matrix}
\
\right]我们定义初等变换有一下三种：
交换任意两行
对于某一行整体乘上一个数
对于任意两行相加或者相减
我们就不难模拟出一下流程
枚举主元，找到主元下面系数不为零的一行（有时为了精度，会选择主 ...
【算法介绍】拉格朗日插值法
算法简介：同袍的义理拉格朗日插值法，是一种已知多项式函数 $f(x)$ 上的 $k$ 个点 $(x_i,y_i)$ 求这个多项式的系数的东西。是以法国十八世纪数学家约瑟夫·拉格朗日命名的一种多项式插值方法。
算法演示：僚佐的才巧算法推导 ：御敌的执定多项式的系数表示法众所周知一个 $k$ 次多项式可以被它的 $k+1$ 个系数唯一地确定，即：
f(x) = \sum\limits_{i = 0}^{k}a_ix^i这种确定多项式的方法叫做多项式的系数表示法。
多项式的点值表示法众所周知，一个 $k$ 次多项式同样的可以被图上的 $k+1$ 个点唯一确定。我们设这个多项式的形式为：
f(x) = \sum\limits_{i = 0}^k a_ix^i那么我们把这几个点带入到这个式子里，就可以得到 $k+1$ 个 $k+1$ 元一次方程组（小学生都知道吧）
\begin{cases}
a_0+a_1x_1+a_2{x_1}^2+\dots+a_k{x_1}^{k}=y_1\\
a_0+a_1x_2+a_2{x_2}^2+\dots+a_k{x_2}^{k}=y_2\\
\dots\ ...
【拾题杂谈】GYM100517F Frequent Permutations
题面大秦为你打开题目传送门
题目描述彼得正在开发新的赌博软件。现在他正在编写一部分软件，可以处理纸牌组。为此，他需要生成从 $1$ 到 $n$ 的整数的随机排列。
不幸的是，彼得不知道这样做的好算法。所以他使用以下算法。首先初始化 $a[i] = i$ 。然后 $t$ 次选择从 $1$ 到 $n$ 的均匀随机 $i$ 和从 $1$ 到 $n$ 的随机 $j$ ，并交换 $a[i]$ 和 $a[j]$ 。
约翰了解了彼得生成随机排列的方法，并决定利用他的知识在赌场获胜。约翰想知道在彼得方法生成的排列中，哪种排列最常发生，它的概率是多少。
请帮助越好找到这个序列以及他的概率。
输入格式输入包含多组数据。
每一组数据输入一行两个整数 $n,t$ 含义如题面 $(\ 1\le n\le 14,0\le t\le 300\ )$ 。
最后一行输入两个零表示读入结束。
输出格式对于每组数据，输出两行，第一行输出出现概率最大的序列，第二行输出它出现的概率，用最简分数表示。
样例输入1233 3 3 4 0 0
样例输出12341 2 3 5/271 2 3 43/243
【拾题杂谈】GYM100517E Exam Scoring
题面大秦为你打开题目传送门
题目描述安德鲁在圣彼得堡国立搜索大学教授算法和数据结构课程，教授信息纳米技术、力学和光学。今天，他正在为他的学生举办笔试。考试包括 $n$ 个必须解决并提交评估的任务。
安德鲁检查了所有学生的考试作业，并了解每个学生和每个任务是否解决了。现在，他想为每个任务分配积分，以便由较少的学生解决的更难的任务获得更多积分。分配给任务的分数必须加起来为 $s$ 。
形式上，设 $a_i$ 为完成第 $i$ 个任务的学生人数，设 $a_i$ 为每个 $i$ 且大于 $0$ 。安德鲁想要一些 $b_i$ ，即 $a_ib_i = c$ 对于所有 $i$ ，其中 $c$ 是常数，$\sum\limits_{i = 1}^{n}b_i = s$ 。
不幸的是，这样的 $b_i$ 可能是分数。安德鲁不喜欢分数，所以他想用最小二乘法用整数 $p_i$ 来近似 $b_i$ 。此外，安德鲁认为给某些任务打得太低或太高都是不公平的。因此，对于给定的 $L$ 和 $U$ ，每个任务的分数必须介于 $L$ 和 $U$ 之间（包括 $L$ 和 $U$ ）。
所以现在安德鲁需要找到整数值 $p ...
