## geometry 设$y=kx+b$与$x$轴负半轴的交角为$\alpha$. 因为$y=kx+b$与$x,y$正半轴相交,所以$\alpha\in[0,\frac{\pi}{2})$. 那么$|PA|=\frac{y}{\sin \alpha},|PB|=\frac{x}{\cos \alpha}$. 那么$|PA||PB|=\frac{xy}{\sin \alpha \cos \alpha}=\frac{2xy}{\sin 2\alpha}$. 因为$\sin 2\alpha \le 1$,所以最小值为$2xy$ ## tree 把每条边权是1的边断开,发现每个点离他最近的点个数就是他所在的连通块大小. 开一个并查集,每次读到边权是0的边就合并.最后$Ans_i=size[findset(i)],size$表示每个并查集根的$size$. ## graph 考虑$dp$,用$f_{t,x}$表示第$t$秒在$x$的概率,初始时$f_{0,u}=1$. $f_{t+1,y}=\sum_{x,x->y}{\frac{f_{t,x}}{Out_x}},Out_x$表示$x$的出度. 因为$t$很大,而且发现每次的转移都是相同的,所以直接矩乘就好了. 复杂度是$O(QN^3\log t)$. ## function 令$S_1(n)=\sum_{i=1}^{n}{i^2-3i+2}=\frac{n(n+1)(2n+1)}{6}-3\frac{n(n+1)}{2}+2n$. $S_2(n)=\sum_{i=1}^{n}{f(i)}$ $S_1(n)=\sum_{i=1}^{n}\sum_{j|i}{f(j)}$ $S_1(n)-S_2(n)=\sum_{i=1}^{n}\sum_{j|i,j<i}{f(j)}=\sum_{j=1}^{n}{f(j)\lfloor \frac{n}{j}-1 \rfloor }$. $S_1(n)-S_2(n)=\sum_{i=2}^{n}{S_2(\lfloor \frac{n}{i} \rfloor)}$ $S_2(n)=S_1(n)-\sum_{i=2}^{n}{S_2(\lfloor \frac{n}{i} \rfloor)}$ 可以在$O(X\log X)$的时间内把$\le X$的$S_2$值都预处理好,然后每次计算的时候将$S_2$的值开一个$hash$记忆化一下. 可以证明当$X=n^{\frac{2}{3}}$时,复杂度是$O(n^{\frac{2}{3}})$的. ## The classic problem 考虑没有不能选的数字的情况. 令答案的多项式是$f(x)$,它的第$x^i$的系数表示和为$i$的方案数. $f(x)=\prod_{i=0}^{n-1} {(1+x^i)}$. 我们要算的是$f(x)~mod~(x^m-1)$这个多项式的常数项. 因为$m$是二的整次幂,而且又是$f(x)~mod~(x^m-1)$,很容易想到$fft$. 根据$fft$算法的意义,计算$f(x)$在$\omega_{m}^{i},i\in[0,m-1]$处的点值然后在逆$fft$回来得到一个$m-1$次的多项式,它的常数项就是答案. 后面一步逆$fft$可以$O(m\log m)$解决. 前面一步就是要计算$f(\omega_{m}^{k})=\prod_{i=0}^{n}{(1+\omega_{m}^{ik})}$. 考虑到单位根的周期性,这个乘积只要计算他前面$m$项的值就好了,后面的根据周期性很容易做. 至于不能选的部分,再算点值的时候用逆元除掉就好了.注意特判0的情况(乘的时候不要把0乘进去,多开一个变量记录0的个数). 这样一个测试点的复杂度就是$O(m^2+ms+m\log m)$.

## N bulbs 我们注意到总的操作次数是跟$n$奇偶的。这个很重要，也就是如果$1$的数量和$n$不同奇偶，那么一定无解。 那么现在问题是$1$和$n$同奇偶的情况下，是不是一定有解？答案是显然的。 因为$1$和$n$同奇偶，所以$0$的个数是偶数，我们发现当我们从$1$走到$i$时，假设我们往回走到左边某个点$k$，再走回来$i$，那么你会发现有且仅有$k$和$i$这两个数被设成没有操作。 也就是说我们可以每次任意选择两个点设成没有操作，然而不需操作的点数是偶数个，所以刚好可以满足。 ## N*M bulbs 我们发现操作数跟$n+m-1$同奇偶，那是不是当$1$的个数跟$n+m-1$同奇偶是就是YES呢？ 答案是肯定的，我们这样看:首先将棋盘黑白染色，就是若$(i,j)$格子，若$(i+j)$是奇数，那么就是黑格子，否则就是白格子。 我们发现我们可以通过一种操作使得从一个格子走到斜方向的任意一个格子。 这个操作很简单，我们假设一个$2*2$的棋盘： 1 2 3 4 我们这样走：$1->2->1->2->4$, $1$就直接走到$4$了，而且不产生任何操作。 也就是同色格子可以互相到达。 然后我们发现如果要操作一个开关，那么最后所在格子颜色一定会改变。 同上面这个例子： 1 2 3 4 假设我们要操作$2$这个格子。 $1->2->1->3$ 我们成功操作了$2$这个格子，但是从白格子转到黑格子了。 也就是说 假设格子$(n,m)$下面有个格子$(n+1,m)$是最后终点，然而每次操作一个格子需要改变一次颜色。 也就是我们从$(1,1)$改变了若干次颜色后，最后颜色一定要和$(n+1,m)$相同。 也就是说$1$的个数要和$(n+1+m)$同奇偶。 也就是说$1$的个数要和$(n+m-1)$同奇偶。 否则无解。 ## Black Jack 我们通过dp计算概率。 我们设$f1[i][j]$表示现在是闲家叫牌，闲家点数$i$，庄家点数$j$。 此时如果叫牌，枚举每一种情况，计算答案即可。 例如抽到$k(1 \leq k \leq 9, i+k \leq 21)$,那么概率贡献就是$f1[i+k][j]*(1/13)$ 假设停止叫牌，那么概率就是$f2[i][j]$。 $f2[i][j]$表示现在轮到庄家叫牌，闲家点数$i$，庄家点数$j$。 如果$j \geq i$直接返回$1$，否则叫牌，像上面一样转移即可。 最后直接判断概率是否大于$0.5$即可。 ## the soldier of love 我们注意到我们求的是每一组至少覆盖一个点的线段数量。 那么我们可以先求一个点都没有覆盖的的线段数量，在用$n$减去即可。 我们把所有点和线段先这样离线处理： 对于每个线段，在他的右端点处记上一个左端点的标记。 对于每组点，在除了第一个点之外的其他点上，记上一个前一个点的标记，同时记录下这个点的编号。 然后从1到10^6扫一遍数轴，对每个点处理所有标记，先处理点的。 对于每一个点，找到他的前一个点，把树状数组中$[p_{now} - 1, p_{pre} + 1]$中的和累积到这个点的编号的答案里面。 然而这个树状数组是记录什么的呢，对于每个点，找到他的线段标记，也就是这个线段的左端点，把左端点的位置在树状数组里面累加。 也就是说，对当前这个位置，树状数组记录的都是右端点在当前点左边的所有线段的左端点的累加和。 就这样$O((n+m_sum)log10^{6})$的时间复杂度解决。 ## merge 首先要搞清楚怎么求这个最小值。 假设我们有很多数$a_1 < a_2 < a_3 < a_4 ... < a_n$。 现在要让a1和an相遇，假设他们在$a_j$和$a_{j+1}$这两点之间相遇，注意这里$j + 1$是下标，那么所用时间就是$max(a_j - a_1, a_n - a_{j + 1}) + (a_j + a_{j + 1}) / 2$ 也就是假设$mid = (a_j + a_{j + 1}) / 2$，那么答案就是$max(mid - a_1, a_n - mid)$ 也就是我们希望这个$mid$越接近$a_1$和$a_n$的中点越好。这个可以用二分解决。 现在处理合并操作，最简单的就是启发式合并，每次都将小的那堆一个个放进去，然后使其有序就可以了，时间复杂度$O(nlognlogn)$ 第二种方法就是线段树合并，线段树维护区间最大最小值和最大最小中点值，合并时更新，询问时类似的分治查找就可以了，时间复杂度$O(nlogn)$

感谢BC验题组和管理员对本场比赛的建议和帮助。 出题人的语文不是很好，导致有些选手对部分题意的理解有误，非常抱歉。 ## GTW likes math 由于是整数区间，直接枚举即可。时间复杂度$O(T*(r-l))$ ## GTW likes gt 首先这道题有一个很显然的$O(n*logn)$的做法，直接区间加，求区间最大值即可。 但是此题还有一个$O(n)$的做法。我们发现$b_1,b_2,...,b_x$都加$1$就相当于$b_{x+1},b_{x+2},...,b_n$都减$1$。然后我们可以倒着做，记一下最大值，如果遇到了修改操作，就把最大值减$1$，然后判断一下这个人会不会被消灭掉，然后再更新一下最大值。 ## GTW likes function 由打表找规律可得，$\sum_{k=0}^{x}(-1)^{k}2^{2x-2k}C_{2x-k+1}^{k}=x+1$，所以显然$f_n(x)=n+x+1$，因此直接求$\varphi(n+x+1)$。时间效率$O(T\sqrt{n})$ 严格证明： 设$a_n=\sum_{k=0}^{n}(-1)^k2^{2n-2k}C_{2n-k+1}^k$ $a_n=2^{2n}+\sum_{k=1}^{n}(-1)^k2^{2n-2k}(C_{2n-k}^k+C_{2n-k}^{k-1})=\sum_{k=0}^{n}(-1)^k2^{2n-2k}C_{2n-k}^k+\sum_{k=0}^{n-1}(-1)^{k+1}2^{2(n-1)-2k}C_{2(n-1)-k+1}^k$ 设$b_n=\sum_{k=0}^{n}(-1)^k2^{2n-2k}C_{2n-k}^k$，则$b_n=a_n+a_{n-1}$ $b_n=2^{2n}+\sum_{k=1}^{n-1}(-1)^k2^{2n-2k}(C_{2n-k-1}^k+C_{2n-k-1}^{k-1})+(-1)^n$ $=4\sum_{k=0}^{n-1}(-1)^k2^{2(n-1)-2k}C_{2(n-1)-k+1}^k+\sum_{k=0}^{n-1}(-1)^{k+1}2^{2(n-1)-2k}C_{2(n-1)-k}^k$ $=4a_n-b_{n-1}$ 得$a_n-a_{n-1}=a_{n-1}-a_{n-2}$。因为$a_0=1,a_1=1$，所以$a_n=n+1$ 证明比较费时，打表找规律能很快的得出解，所以本题的关键在于打表找规律。 ## GTW likes czf 首先会发现x @ y=$x\ xor\ y$，(ps:出题人很良心，在样例解释里暴露了这一事实) 并且一个数字和其它若干个不同的数字$xor$的结果肯定是互不相同的，所以最后的答案就是$(r-l+1)*2-$重复数字。 那么如何求重复数字呢。显然需要满足$g\ xor\ x=t\ xor\ y$，$x$和$y$是我们从区间$[l,r]$中挑出来的数字，通过移项，就变成了$g\ xor\ t=x\ xor\ y$，所以我们要求$[l,r]$中有多少对$x,y$异或等于$g\ xor\ t$这个东西显然可以数位dp。 我们用$f[i][a][b][c][d]$表示做到了第$i$位二进制，$x$的取值范围是$a$到$b,y$的取值范围是$c$到$d$的方案$(0\leq a\leq b\leq 1,0\leq c\leq d \leq 1)$，然后分情况讨论一下，如果$g\ xor\ t$的第$i$位是$1$，那么$x$和$y$的第$i$位肯定一个$0$，一个$1$，如果$g\ xor\ t$第$i$位$=0$，那么$x$和$y$的第$i$位肯定相同，然后我们可以确定新的$a,b,c,d$的取值范围，然后继续做第$i-1$位。 总的时间复杂度$=O(T*60*2*2*2*2)$ 加了强力剪枝的搜索也是可以通过本题的。 然而好像只有yjqqqaq是写标算的。 ## GTW likes tree 最后答案为所有至少经过一个特殊点的路劲的$Dis$值累乘起来。 我们先不考虑特殊点。 首先我们发现$a[i]\leq 100000$，所以每一个$a_i$最多只会有$6$个不同的质因子(ps:因为$2*3*5*7*11*13*17>100000$) 这道题看起来很像点分，然而出题人太笨了，只会$O(n*log_{2}{n}*6*log_{2}{log_{2}{100000}})$的方法(ps:可能有复杂度更优的点分)，然而这个方法被卡掉了。 因为答案是所有$Dis$累乘起来，所以可以把每一个质因子分开做，最后答案乘起来即可。 设当前正在做的质数为$x$，先从高到低枚举它的幂次，假设现在枚举的幂次为$p$，找出所有点权是$x^p$的倍数，但不是$x^{p+1}$的倍数的点(这个可以预处理)，然后算一下通过这个点的路径数量$sum$，答案乘以$x^{p*sum}$。这个可以用并查集维护。(ps：此处有一个小优化，可以把每个质数的幂次都乘起来，最后每个质数做一遍快速幂即可) 接下去来考虑特殊点，最后的答案就是所有路径$Dis$的乘积/不经过特殊点的路径$Dis$的乘积，所以只要先求一遍答案，然后把特殊点删掉，再求一遍答案，两个答案相除即可。 时间效率$O(T*n*\alpha *6)$

## ZYB's Biology 直接按照题意模拟即可. ## ZYB's Game 我们会发现这个模型其实是类比于左右两堆石子,每次可以在一堆里取任意多,取完的人胜利.当左右两堆石子相同时,我们可以简单的 构造后手胜利的方法:即在另一堆石子中取走同样多的石子,否则,先手可以取一些石子使得两堆石子相同.所以,当$N$是奇数输出$1$,否则输出$0$. ## ZYB's Premutation 设$f_i$是第$i$个前缀的逆序对数,$p_i$是第$i$个位置上的数,则$f_i-f_{i-1}$是$i$前面比$p_i$大的数的个数.我们考虑倒着做,当我们处理完$i$后面的数,第$i$个数就是剩下的数中第$f_i-f_{i-1}+1$大的数,用线段树和树状数组可以轻松地求出当前第$k$个是$1$的位置,复杂度$O(N \log N)$. ## ZYB's Tree 因为$N$很大,所以点分治会跑的比较慢.但是我们可以发现$K$很小,所以我们随便定一个根,令$f[i][j]$为第$i$个点的子树中深度和$i$不超过$j$的数的个数.然后我们枚举每个点距离不超过$k$的祖先,然后对于第$j$个祖先,答案加上不在$i$所在的子树中,深度不超过$k-j$的点的个数,复杂度$O(NK)$. ## ZYB's Prime 如果没有$1$的情况,因为每个环中数的个数$\geq 3$,而且肯定是一奇一偶交替,我们考虑把奇偶分成两列,然后原点向每个奇数连流量为$2$的边,每个偶数向汇点连流量为$2$的边,分别对应一个数周围有两个数,然后每个奇数向和它相加是质数的偶数连流量是$1$的边,如果一条边流过就代表这两个数相邻,如果我们顺着流量走,就会走到一些$size \geq 3$的环,这些环对应的就是答案.如果奇偶数的个数不相等或者不是满流,那么就是不合法的，否则就是合法的. 现在来考虑$1$的情况,我们会发现$1$的特殊性是一些$1$并在一起当成一个$1$用,其他和奇数无异.其实我们可以用$1$去填充那些不够的奇数.如果非$1$奇数个数原本就大于偶数或者奇数个数比偶数个数小,显然是不合法的,否则我们就可以填上一些$1$,然后做没有$1$的情况,剩余的$1$可以被塞到任意一个$1$中.本题有一个$trick$是当需要加的$1$的个数是$0$时,需要判断剩下的$1$的个数能不能自成一个环,如果有$1$且$1$的个数$\leq 2$,那么也是不合法的. 但是这样真的就是对的了么?事实上,当形如$1 \ 1 \ 1 \ 1 \ 6 \ 1$的数据出现时,我们现在的程序是无法得到答案的,因为我们只有一个$1$,而这个$1$和$6$形成的是一个二元环. 但是容易证明的是,当存在$1 \ 1 \ 1 \ X \ 1$的情况时,这个环里必定包含了所有的$1$.否则,我们可以将这个环拆开加入到其它的$1$中,这样就得到了一个没有这种情况的新解. 所以我们只要把所有的$1$都缩成一个点,然后这个点向其它可连边的偶点连$2$的边,再跑一遍网络流即可.不必担心这个点出去$2$条流量为$1$的边,事实上这种情况和第一次是完全等价的.

感谢验题组的建议和帮助。 ## Numbers 判断是否是2或者5的倍数只看最后一位，判断3时统计十进制下每一位之和是否是3的倍数。 ## Sum 令${A}_{i}=f({A}_{i})-{A}_{i}$,然后求一遍最大连续子序列和就能知道最多能增加的值。 ## Array 其实${A}_{i}$为i二进制中1的个数。每次变化${A}_{k+{2}^{i}}={A}_{k}+1$ ,$(k<{2}^{i})$不产生进位，二进制1的个数加1。然后数位dp统计前m个数二进制1的个数，计算每一位对答案的贡献。只需考虑该位填1，其高位与低位的种数即可。 ## Strings 问题转化成一颗完全m叉树，节点和从左到右m个儿子的边权分别是1到m，求n个互不为祖先的节点的最小权值和。代价为i的节点个数将为指数级，所以选取的节点代价最大不超过$logN$级别。将当前子树叶子节点按代价排序，最优解下选取的节点必然是连续的一段。枚举选取的最小节点代价k为多少，用$Fi$记录当前代价为i的叶子节点数量，小于k的节点必然化成其儿子作为叶子，则可以三分多少个k代价节点转化成其儿子的值最优。 ## Tree 以1为根遍历一遍，记录${X}_{i}$为$f(1,i)$的值，那么$f(i,j)={X}_{i} \ xor \ {X}_{j}$。于是容易想到莫队算法，问题就变成如何快速计算一个数x分别和其他若干个数异或和大于m的数量。把这些数转化成二进制，然后从高位到低位加入字典树，字典树维护每个节点下叶子的数量。若x和其他数异或和y大于m，则必然是y与m二进制下有一位不同，在这一位中y为1而m为0并且更高位都相同。只需要枚举第一个不同位就能根据字典树算出异或和大于m的数量。复杂度$O({N}^{\frac{3}{2}}logM)$