如果存在一组匹配能够覆盖左部点集合 $X$，且存在一组匹配能覆盖右部点集合 $Y$，我们猜测 $X\cup Y$ 也能被一组匹配覆盖。

我们构造一个新图，对于原图上能覆盖 $X$ 的匹配中的一条边 $(u,v)$，我们在新图上连有向边 $(u,v)$；对于原图上 $Y$ 的匹配中的一条边 $(u,v)$，我们在新图上连有向边 $(u,v)$。不难发现新图上所有点的入度不超过 $1$。所以新图上的每个弱连通块都形如一条链或一个环。

对于原图上的一条极长链 $(u_0,u_1),(u_1,u_2),\cdots,(u_{k-1},u_k)$，我们不失一般性地假定 $u_{k-1}\in X$，那么显然 $u_k\not\in Y$，否则链不会在此终止。

如果 $k$ 是奇数，我们取 $(u_0,u_1),(u_2,u_3),\cdots,(u_{k-1},u_k)$ 作为一组匹配；如果 $k$ 是偶数，我们取 $(u_0,u_1),(u_2,u_3),\cdots,(u_{k-2},u_{k-1})$ 作为一组匹配。不难发现这样一定能覆盖该链上所有在 $X\cup Y$ 中的点。

环同理，交替选取构造匹配即可。

于是根据霍尔定理，两部分别状压判断即可。

对于数论函数 $f$ 定义前缀和 $S_f(n)=\sum_{i=1}^nf(i)$。

如果有两个数论函数 $f,g$ 满足我们可以快速计算 $S_g$ 和 $S_{f*g}$，可以通过杜教筛快速求出 $S_f(n)$。

$$\displaylines{\begin{aligned} S_{f*g}(n)=&\sum_{i=1}^n\sum_{d|i}g(d)f\left(\frac id\right)\\ =&\sum_{d=1}^ng(d)\sum_{k=1}^{\lfloor\frac nd\rfloor}f(k)\\ =&\sum_{d=1}^ng(d)S_f(\left\lfloor\frac nd\right\rfloor) \end{aligned} }$$

于是有

$$\displaylines{g(1)S_f(n)=S_{f*g}(n)-\sum_{d=2}^ng(d)S_f(\left\lfloor\frac nd\right\rfloor) }$$

直接利用该式记忆化地递归求解，因为

$$\displaylines{\left\lfloor\frac{\lfloor\frac n{d_1}\rfloor}{d_2}\right\rfloor=\left\lfloor\frac n{d_1d_2}\right\rfloor }$$

所以我们只在所有 $\lfloor\frac nd\rfloor$ 处求了 $S_f$ 的值（其中 $d$ 是 $[1,n]$ 内的整数），每次求值使用整除分块，将 $d$ 以 $\sqrt n$ 为界分开考虑，总复杂度如下：

$$\displaylines{\begin{aligned} &O\left(\sum_{i=1}^{\sqrt n}\sqrt i+\sum_{i=1}^{\sqrt n}\sqrt\frac ni\right)\\ =&O\left(\int_0^{\sqrt n}\sqrt x\mathrm dx+\int_0^{\sqrt n}\sqrt\frac nx\mathrm dx\right)\\ =&O\left(\left.x^{\frac32}\right|_0^{\sqrt n}+\left.\sqrt{nx}\right|_0^{\sqrt n}\right)\\ =&O\left(n^\frac34\right) \end{aligned} }$$

如果 $f$ 可以通过线性筛预处理出不超过 $K$ 的 $S_f$ 值，复杂度可以进一步优化。因为只求所有不超过 $\sqrt n$ 处的 $S_f$ 值已经达到了 $O(n^\frac34)$ 的复杂度，所以想要优化复杂度，$K$ 至少为 $\sqrt n$。所以有

$$\displaylines{\begin{aligned} &O\left(K+\sum_{i=1}^\frac nK\sqrt\frac ni\right)\\ =&O\left(K+\left.\sqrt{nx}\right|_0^{\frac nK}\right)\\ =&O\left(K+nK^{-\frac12}\right) \end{aligned} }$$

$K=O(n^\frac 23)$ 时复杂度平衡，为 $O(n^\frac 23)$。

素性测试

二次探测定理：对于质数 $p$，方程 $x^2\equiv1\pmod p$ 的解只有 $x\equiv\pm1\pmod p$。

证明：$(x+1)(x-1)\equiv x^2-1\equiv1\pmod p$，于是 $p\mid(x+1)(x-1)$。由于 $p$ 是质数，$p\mid x+1$ 或 $p\mid x-1$ 至少有一个成立。$\square$

这意味着，如果我们想判定 $p$ 的素性，我们可以尝试找出 $x\not\equiv\pm1\pmod p$ 而 $x^2\equiv1\pmod p$ 的 $x$。一旦我们找出了一个这样的 $x$，$p$ 一定不是素数。而在经过大量检测后没有找到这样的 $x$，我们即宣称 $p$ 是素数（并且我们确实能够证明这样做的正确性）。

考察费马小定理 $a^{p-1}\equiv1\pmod p$，其中 $p$ 为素数。我们将 $p-1$ 表示为 $2^sd$，其中 $d$ 为奇数。

如果我们任选一个 $(0,p)$ 内的整数作为底数 $a$，将 $d,2d,4d,\cdots,2^{s-1}d$ 分别代入 $x$，如果有 $a^{2^kd}\not\equiv\pm1\pmod p$ 而 $a^{2^{k+1}d}\equiv1\pmod p$ 则说明 $p$ 不是质数。如果 $a^{p-1}\not\equiv1\pmod p$ 也说明 $p$ 不是质数。

可以证明，能够将一个非质数 $n$ 判别出来的底数 $a$ 至少有 $\left\lfloor\frac{n-1}2\right\rfloor$ 个。也即在 $(0,n)$ 中随机选取 $a$，将非质数判别为质数的概率不超过 $\frac12$，那么随机选择多个底数分别判断即可达到较高正确率。

如果广义黎曼猜想成立，只需以 $[2,\min\{n-2,\lfloor2\ln^2n\rfloor\}]$ 的所有数分别作为底数 $a$ 进行探测，即可确定 $n$ 的素性而不依赖于概率分析。而对于 OI 中常见的 $[1,2^{64})$ 中的所有数，只用不超过 $40$ 的 $12$ 个质数即可。

分解质因数

对于合数 $n$，通过枚举获取 $n$ 的因数是困难的，可以考虑以一定的方式生成一些 $k$，通过求 $\gcd(n,k)$ 获取 $n$ 的非平凡因子。那么我们要做的就是尽量减小 $\gcd(n,k)$ 为 $1$ 或 $n$ 的概率。

考虑数列 $a_0=0,a_i=(a_{i-1}^2+c)\bmod n$，其中 $c$ 是 $(1,n)$ 内的任意整数。设 $n$ 有某一因子 $k$。显然数列 $\{a_i\bmod k\}$ 一定会在有限项内进入循环。而 $a_i\bmod k=a_j\bmod k$ 意味着 $k\mid a_i-a_j$，此时如果 $n\nmid a_i-a_j$ 的话，$\gcd(n,a_i-a_j)$ 即为 $n$ 的一个非平凡因子，否则分解失败。

具体实现有两种。

第一种实现本质上是 Floyd 判环算法，从小到大枚举 $i$，如果某次 $k=\gcd(a_i-a_{2i},n)$ 不为 $1$，说明数列 $\{a_n\bmod k\}$ 在第 $i$ 项之前已进入循环。

第二种实现是利用倍增，将两个指针 $s,t$ 初始设为 $0$，第 $i$ 轮 $t$ 向后移动 $2^{i-1}$ 步，每步之后检查 $\gcd(n,s-t)$，该轮结束后将 $s$ 赋为 $t$。为了进一步优化常数，每 $127$ 步检验近 $127$ 步中 $s-t$ 的累乘结果。实验表明，$127$ 是一个很好的参数，过小会导致求 $\gcd$ 的次数较多，过大会导致累乘结果得到 $0$ 的概率过大，频繁失败。

两种实现的期望复杂度均为 $O(m\log a)$。其中 $m$ 为 $\min_{d|n}\#\{a_i\bmod d\mid i\in\mathbb N\}$ 在 $c$ 均匀随机时的期望。首先该值一定小于 $\#\{a_i\bmod k\mid i\in\mathbb N\}$，其中 $k$ 为 $n$ 的最小质因子。

那么期望多少项 $\{a_i\bmod k\}$ 会开始循环呢？首先我们发现该数列在 $(1,k)$ 内的分布较为均匀（这也是选择 $(x^2+c)\bmod n$ 来生成数列下一项的原因），所以该数列进入循环的项数等同于不断在 $k-1$ 个元素中均匀随机选取，第一次取到已经出现过的数的期望次数。

在 $n$ 个元素中进行 $t$ 次选择结果两两不同的概率为 $P=\prod_{i=0}^{t-1}\frac{n-i}n$，由 $1+x\le e^x$ 有

$$\displaylines{P=\prod_{i=0}^{t-1}\frac{n-i}n\le\prod_{i=0}^{t-1}\exp\left(-\frac in\right)=\exp\left(-\frac{t(t-1)}{2n}\right) }$$

于是对于 $p\in(0,1)$，

$$\displaylines{P\le p\Longleftarrow\exp\left(-\frac{t(t-1)}{2n}\right)\le p\iff t(t-1)\ge-2n\ln p\Longleftarrow t\ge\sqrt{-2n\ln p} }$$

将 $t$ 次选取看作一次实验，根据独立随机试验的结论，这样的实验失败一次的期望次数为 $\frac1{1-p}$，故在 $k-1$ 个元素中随机选取，直到得到相同元素的期望次数不超过

$$\displaylines{\frac1{1-p}\sqrt{-2(k-1)\ln p}=O(\sqrt k) }$$

于是该算法的复杂度为 $O(m\log a)=O(\sqrt k\log a)=O(\sqrt[4]n\log a)$。

SNOI2024 游记，PKUWC2024 游记，WC2024 游记，和若干仍被悬置着的问题的讨论。

我还记得考前的那晚，教练赶所有人回家，我偷偷跑到五楼教室听马勒《第六交响曲》。我倒不甚紧张，而是感到决定我人生走向的大事即将发生的一种庄严，一种平静。我感到未来的我正凝视着此刻。

《第六交响曲》，悲剧，西西弗斯式永无止境的循环，惊涛骇浪下苦苦挣扎的个体。

听第三乐章正酣，教练来了，看到戴着耳机一脸陶醉的我，敬畏地把我送出教室，嘱咐我放平心态，晚上早睡。

我很谔谔啊！推着车子走出学校大门，回头望见显眼的红色横幅：NOI 2024 省队选拔陕西赛区考点。拍了张照发空间。

我有癔症。总是喜欢幻想着别人怎么看待自己，别人怎么评价自己。

所以我不禁想，我这次考进了省队，父母会怎么看我呢，机房里的同学会怎么看我呢，文化课那边仅仅只是见过几面的同学们会怎么看我呢，初中的老师朋友仇人又会怎么看我呢；如果我没考进省队，他们又会怎么看我呢。

我被凝视着，亦或是我幻想自己被凝视着，并且以幻想自己被凝视为乐。

那场比赛我具体经历了啥，已经快忘了，好像是很不在状态来着。最后的结果是，六道题，三道暴力写挂。差一名还是两名，被据之“队”外。

我至今也想不明白这个成绩是怎么打出来的，太离谱了。

其实我无意识中一直萦绕着一点迷茫，随着省选的落败，它渐渐地浮出来了。

我为什么要学信息竞赛？

小学的时候喜欢编程，是迷恋上了这种具有无穷创造力的魔法；小升初那会喜欢算法，是因为它能够带给我许多新奇的思考；初一初二喜欢信息学竞赛，因为我似乎在这方面发现了我有巨大的潜力……是吗？

我常常自我否认的一点是，我学竞赛其实是为了拿金牌，保送清华北大，然后，然后，被同学们，被老师们，被一切以前不看好我的人，刮目相看。

都说了，我有癔症。我以将自己置于他者的凝视之下享乐。

学了竞赛才发现，比我聪明比我努力的人多的是。而我只会做白日梦，幻想自己所欲望的一切，却在面对争取它们的机会时，犹豫退缩。

或许窝在机房里听马勒，和那些单相思的恋人深夜躺在床上听伤心情歌来自我悲悯，是同样的性质吧。

---

省选结束后不到一个月就坐动车到重庆了。正常发挥吧，除了 Day1 T3 暴力没打导致没达到大众分。得奖情况直到现在还没公布。

以及 Day2 T3，数据结构功底发力了，让我在一个小时之内写+调完一道线段树套可持久化平衡树，并且通过玄学调参卡空间，幸运地获得了 100pts 的好成绩。

在 PKUWC 的时候认识了不少人，换了若干徽章。

后来搬着行李住进了育才的宿舍。很激动，领了胸牌、书包、冲锋衣、讲义和活动指南，绕了学校一圈，进了宿舍。

路上听到抱怨宿舍没有插座、环境不好的声音此起彼伏，我却丝毫无所谓，反而兴奋极了。下午换了很多徽章，别满了书包。

第一天晚上几乎没咋睡，最后一次看时间是将近一点，凌晨四点起，不过后面睡习惯了就好多了。

讲课是纯纯的听不懂，不过也能勉强学到点新东西，开拓思维什么的。食堂的饭很好吃，赞美育才食堂！

考试也是发挥平平，甚至小挂了点分。看到来 WC 的初二初三一个个都比我考得好，再一次深刻地认识到了竞赛道路的压力巨大。

WC 提供了乒乓球和羽毛球的场地和器材，和 LDL 老哥去打了几个小时来着。

最后颁奖环节是得了奖的所有选手按照分数从低到高依此上台领奖。我擦线铜牌，坐第一排，还是第一批上去领的，太耻辱了。

---

印象最深刻的是快结束的那几天的某个晚上寝室四个人睡不着，开始谈论人生志向。

还是那个问题。你为什么要学信息竞赛？

有人说是纯功利性的，为了保送，或者走强基。有人说学信息竞赛能让他获得一定的自由。

我想了想，突然发现，高中以来学习竞赛，某种意义上是为了逃避文化课。

自从我初三成绩下降，中考暴毙以来，我对文化课产生了深深的厌烦和恐惧。

并且我一直在别人面前以所谓“竞赛佬”的身份示人，在文化课考一次试就足够让我的形象破灭。

所以我是被自己胁迫着来学竞赛的吗？我也有点迷惑了。

或许我还是爱着这一切的吧。或许我只是暂时迷失了方向。

那天晚上我也想明白了不少事情。人活这一辈子干嘛？斗争。和困难斗争，和考验斗争，和历史斗争。

我甚至激动地站了起来，和室友夸夸其谈。

力量来源于信念。有了信念，诸如“为什么要学竞赛”这种问题都显得平庸了。

朝着那个方向，奔跑吧。

fail 数上的子树更改或查询是易于维护的，而对一个字符串在 AC 自动机上经过的路径进行更改或查询只能暴力做。

所以如果直接把 CF547E 的做法用到这里来，区间询问拆成前缀，对每个前缀按顺序处理，fail 树上子树加，每个询问在 AC 自动机上暴力求和，时间复杂度为 $O(A\sum|s_i|+B\sum|s_{t_i}|)$。其中 $t_i$ 为第 $i$ 次询问的文本串，$A$ 为区间加的时间复杂度，$B$ 为单点查询的时间复杂度。注意式子中第一个 $\sum$ 是有约束的（不超过 $10^5$），而第二个没有。这样我们就获得了一个与文本串串长相关的暴力做法。

注意到第一个做法的问题在于遍历文本串的次数过多。如果选择每个文本串只进行一次遍历，对经过的所有点做 $O(1)$ 子树加（树上前缀和），然后依此处理该文本串相关的所有询问，这个做法的时间复杂度为 $O(\sum|s_{t_i}|+|t|\sum|s_i|)$，$t$ 为询问的文本串序列。

于是我们根号分治：对于长度不超过 $\sqrt{\sum|s_i|}$ 的串使用第一种算法，使用 $A=O(\sqrt n),B=O(1)$ 分块进行区间加单点查；否则使用第二种算法，此时 $|t|=O(\sqrt{\sum|s_i|})$。总时间复杂度为 $O((\sum|s_i|)^{1.5})$

中位数的性质是离不开它的排名的，所以常见的处理中位数最值的办法是二分答案。一个长为 $m$ 的序列中，（本题所定义的）中位数大于等于 $k$ 当且仅当小于 $k$ 的数的个数少于 $\left\lceil\frac m2\right\rceil$ 个。

于是这个问题就变成了，是否存在一个左端点在 $[a,b]$ 间，右端点在 $[c,d]$ 间，小于 $k$ 的数的个数少于某个与区间长度相关的值。

注意到此时限制是与区间长度相关的，难以对所有区间进行统一的处理。我们尝试对问题变形，设长为 $m$ 的区间中有 $t$ 个小于 $k$ 的数：

$$\displaylines{t<\left\lceil\frac m2\right\rceil\iff2t<m\iff(m-t)-t>0 }$$

此时式子的含义已经很明确了，中位数大于等于 $k$ 当且仅当区间中大于等于 $k$ 的数的个数减去区间中小于 $k$ 的数的个数大于 $0$。

于是可以用可持久化线段树维护，第 $i$ 个版本对应原序列中第 $i$ 小的数 $x$，线段树上某个位置小于 $x$ 赋为 $-1$，大于等于 $x$ 赋为 $1$，线段树上维护区间和、最大前缀和、最大后缀和，这样每个询问应对的所有区间的和的最大值可以通过线段树快速地求出。

看到异或求和，考虑拆位计算 $v+d(c,x)$ 的第 $k$ 位。不难发现它随着 $d(c,x)$ 每增大 $2^k$ 改变一次。

这启示我们对于每个点考察它对所有祖先的贡献。于是我们要做的第一步是树上差分，将一系列深度相差 $2^k$ 的祖先的差分值异或 $1$。

这个操作不能暴力做。考虑用一个桶对于每个 $i$ 记录某个点的所有祖先中，深度 $\bmod2^k=i$ 的点的差分值。但是这样子树需要向父亲贡献一个合并复杂度为 $O(s)$（$s$ 表示子树大小）或 $O(2^k)$ 的信息，取决于考虑子树内每个点对桶的贡献，还是直接使用子树的桶在对应位置相加。前者可以用树上启发式合并优化。

更好的做法是维护子树内可减信息的经典 trick（天天爱跑步）：

维护一个全局桶，子树跟处只需要记录自己关心的某个位置的值，在遍历子树前和遍历子树后的差，即可求得子树内对桶该位置的贡献。

对于任意两个长为 $N=2^m$ 的数列 $a,b$，令

$$\displaylines{c_i=\sum_{i=p\oplus q}a_pb_q }$$

欲构造可逆线性变换 $\mathcal F_m$，对于所有 $i\in[0,N)$ 满足

$$\displaylines{\mathcal F_m(c)_i=\mathcal F_m(a)_i\cdot\mathcal F_m(b)_i }$$

我们考察 $\mathcal F$ 的矩阵表达 $T$，将 $a,b,c$ 写作列向量 $\mathbf{a,b,c}$，即

$$\displaylines{(T\mathbf c)_i=(T\mathbf a)_i(T\mathbf b)_i }$$

再展开得

$$\displaylines{\begin{aligned} (\sum_jT_{i,j}c_j)&=(\sum_jT_{i,j}a_j)(\sum_jT_{i,j}b_j)\\ \sum_{p,q}T_{i,p\oplus q}a_pb_q&=\sum_{p,q}T_{i,p}T_{i,q}a_pb_q \end{aligned}}$$

为了让 $\mathcal F$ 对于任意的 $a,b$ 都满足这样的性质，每项 $a_pb_q$ 前的系数都要相等，即对于任意 $i,p,q$ 都有

$$\displaylines{T_{i,p\oplus q}=T_{i,p}T_{i,q} }$$

不难发现 $T$ 的每一行都由这样一个方程组限制：

$$\displaylines{\begin{cases} x_{p\oplus q}=x_px_q&\forall p,q\in[0,N) \end{cases} }$$

为了使得 $\mathcal F$ 可逆，我们需要对该方程组求出 $N$ 组线性无关的解。

---

首先有 $x_0^2=x_0$，解得 $x_0$ 为 $0$ 或 $1$。由于 $x_0=0$ 会导致所有 $x_i$ 都为 $0$，与任意一组解皆线性相关，舍去。

然后有 $x_i^2=x_0=1$，解得 $x_i=\pm1$。于是 $f(i)=x_i$ 为 $(S,\oplus)$ 到 $(\{0,\pm1\},\times)$ 两个线性空间之间的同态，其中 $S$ 表示在 $[0,N)$ 内的自然数。

于是我们取出 $(S,\oplus)$ 的一组基，指定集合中每个元素的 $x$ 值后即可得到每个位置的解。简单起见，我们指定

$$\displaylines{T_{i,2^j}=\begin{cases} 1&(\left\lfloor\frac i{2^j}\right\rfloor\bmod2=0)\\ -1&(\left\lfloor\frac i{2^j}\right\rfloor\bmod2=1)\\ \end{cases} }$$

$\left\lfloor\frac i{2^j}\right\rfloor\bmod2$ 即 $i$ 二进制下第 $j$ 位上的数字。

通过观察不难发现，$T_{i,j}$ 的值即为 $(-1)^{\mathrm{popcount}(i\operatorname{AND}j)}$，其中 $i\operatorname{AND}j$ 表示按位与，$\mathrm{popcount}$ 表示二进制下 $1$ 的个数。

更进一步地，按照 $i,j$ 的二进制下第 $m-1$ 位分类讨论，可以将 $T_{i,j}$ 划分为四个方阵。可以看出 $\mathcal F_m$ 的矩阵表示 $T$ 与 $\mathcal F_{m-1}$ 的矩阵表示 $A$ 存在一定关系：

$$\displaylines{T=\begin{bmatrix} A&A\\A&-A \end{bmatrix} }$$

因此求 $\mathcal F_m(a)$ 也可以依此递归进行，将 $a$ 等分成两份 $a_0,a_1$，于是 $\mathcal F_m(a)$ 的前半部分为 $\mathcal F_{m-1}(a_0)+\mathcal F_{m-1}(a_1)$，后半部分为 $\mathcal F_{m-1}(a_0)-\mathcal F_{m-1}(a_1)$。这里的加减表示序列对应位置相加减后得到一个新序列。

为了求 $T$ 的逆，我们进行消元：

$$\displaylines{\left[\begin{array}{cc|cc}A&A&1&0\\A&-A&0&1\end{array}\right] \rightarrow\left[\begin{array}{cc|cc}A&A&1&0\\0&-2A&-1&1\end{array}\right] \rightarrow\left[\begin{array}{cc|cc}A&0&\frac12&\frac12\\0&-2A&-1&1\end{array}\right] \rightarrow\left[\begin{array}{cc|cc}1&0&\frac12A^{-1}&\frac12A^{-1}\\0&1&\frac12A^{-1}&-\frac12A^{-1}\end{array}\right] }$$

即

$$\displaylines{T^{-1}=\frac12\begin{bmatrix}A^{-1}&A^{-1}\\A^{-1}&-A^{-1}\end{bmatrix} }$$

此时

$$\displaylines{T_{i,j}=\frac{(-1)^{\mathrm{popcount}(i\operatorname{AND}j)}}{2^n} }$$

也即得到了 $\mathcal F$ 的逆变换。

如果存在凸函数 $f(x)$，我们无从得知其在某个 $x$ 处的值，但是可以求出某个斜率的直线切它时切点的位置。注意到切点的横坐标关于直线斜率存在单调性，可以依此二分，找出任意一个与凸包切于该点的一次函数，即可计算出该函数在某个 $x$ 处的值。

对于每个子树，显然下端点不在子树内的链不会对子树内部的覆盖情况产生影响，所以我们将所有下段点在子树内的链构的集合的一个能够完全覆盖该子树的子集称作一种合法方案；将一种合法方案的下段点最靠上的链称作最浅链。

我们要对于每颗子树的每种可能的最浅链取值，维护权值最小的合法方案。

儿子转移向父亲的过程中，需要加入答案最小的以下段点为儿子的链为最浅链的方案。此时贪心地选择子树内维护的所有合法方案中答案最小者，加上该链贡献即可。

多个儿子合并时，如果某条链被钦定为父亲答案中的最浅链，除了该链下段点所在的儿子子树，其余儿子子树中贪心选择所有合法方案中最小值即可。如果其余子树中的方案选择使得该链最终不是最浅链，这样构造出来的错误方案一定不优于钦定真实的最浅链为最浅链构造出来的方案，所以无关紧要。

于是我们需要这样一种数据结构：能够快速求出集合中最小值，快速给集合权值整体加 $k$，合并若干集合。因此使用可并堆。

至于在转移过程中不能完全覆盖子树而变得不合法的方案，可以 lazy 地进行弹出。即使用到某个集合最小值时再判断其合法性，不合法则弹出。