HDU分析令 $p_{a_i}=i$,则题目要求的是考虑莫队,加入一个数时枚举约数更新贡献即可。时间复杂度 $\mathcal{O}(\text{能过})$。当然你 $\mathcal{O}(\sqrt{n})$ 枚举约数当然是过不了的,可以开一个 vector 存下所有约数。代码// =================================== // author: M_se...
SPOJLuogu分析树上莫队板子题...?首先把树的欧拉序爬下来。设 $st_u$ 表示第一个 $u$ 的位置,$ed_u$ 表示最后一个 $u$ 的位置。考虑一个询问 $(u,v)$ 怎么统计。为了方便,设 $st_u<st_v$ 。如果 $lca(u,v)=u$ ,那么 $(u,v)$ 路径上的点就是欧拉序的 $[st_u,st_v]$ 中只出现过一次的点,莫队统计即可。如果 $...
破解D-H协议$\begin{cases}g^a\equiv A\pmod{P}\\g^b\equiv B\pmod{P}\end{cases}$ 直接上 $\mathrm{BSGS}$ 求出 $a$ 和 $b$ ,然后答案就是 $g^{ab}\bmod P$ 。代码社交网络【模板】有向图矩阵树定理。代码交错序列首先推式子: $x^ay^b=(n-y)^ay^b=\sum\limits_{i...
CodeForcesLuogu分析如果在序列上这个问题非常的好做:设 $num[i]$ 为 $i$ 颜色的数量, $sum[i]$ 表示颜色数量 $\geq i$ 的颜色数。那么直接跑莫队即可。现在放到了树上变成了子树询问,那么直接在 dfs 序上跑就好了。当然 dsu on tree 也是可以的。具体实现及细节见代码。代码// ===============================...
LuoguBZOJ分析莫队+ $\mathrm{bitset}$。显然一个询问 $(l_1,r_1,l_2,r_2,l_3,r_3)$ 的答案是 $(r_1-l_1+1)+(r_2-l_2+1)+(r_3-l_3+1)-3\times size$ ,这里的 $size$ 表示三个区间内出现了多少个公共的颜色。前面的非常 $\mathrm{sb}$ ,重点是怎么求 $size$ 。如果我们用...
LuoguBZOJLOJ分析这样子就可以把每个询问拆成四个,然后莫队即可。代码//It is made by M_sea #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include ...
LuoguBZOJ分析记 $s[i]=a[1]\oplus a[2]\oplus ... \oplus a[i]$ 。问题变为 $[l-1,r]$ 中,有多少对 $(x,y)$ 满足 $s[x]\oplus s[y]=k$ 。莫队即可。代码//It is made by M_sea #include <algorithm> #include <iostream> #i...
LuoguBZOJ分析莫队 Day2两个莫队题海星。首先考虑怎么判断 $[l,r]$ 能被 $P$ 整除。设 $num[i]$ 表示 $i\sim n$ 所构成的数。如果 $[l,r]$ 能被 $P$ 整除,那么有 $\frac{num[l]-num[r+1]}{10^{r-l+1}}\equiv0\pmod P$。这里可以分类讨论一下了。当 $P\neq 2$ 且 $P\neq5$ 时此时...
LuoguBZOJ分析莫队。重点是两个状态怎么 $O(1)$ 的转移。先来考虑从 $[l+1,r]$ 转移到 $[l,r]$ 的情况。这样子会多出来 $[l,l],[l,l+1],...,[l,r]$ 这些区间,我们来考虑这些区间的答案。先找到这段区间的最小值 $p$ ,那么右端点在 $[p,r]$ 之间的区间的贡献都是 $a[p]$ 。还剩下右端点在 $[l,p-1]$ 的情况,把这一部分...
LuoguBZOJ分析莫队。假如第$i$种袜子有$cnt[i]$个,那么抽到一双的概率是莫队维护一下分子就行。考虑一下$cnt[i]$增加/减少时答案发生了什么变化。大力推一发可以发现增加/减少了$2\cdot cnt[i]$。细节见代码。代码#include <algorithm> #include <iostream> #include <cstdlib&g...