P3338

考虑翻转序列以凑成卷积的形式，然后 FFT 做。

P9407

神仙题。考虑

\[\int_0^{\pi}l\lvert\cos\theta\rvert d\theta = 2l \]

也就是说，每条线段在直线 \(y=\tan\theta\) 上的投影长度在 \(\theta\in[0,\pi]\) 上的定积分为 \(2l\)。于是考虑均匀取样若干角度映射为一维问题近似求出答案，这个操作被称为黎曼和。

P5491

二次剩余模版。

  1. 对于奇素数 \(p\)，二次剩余 \(n\) 的数量恰为 \(\frac{p-1}{2}\) 个，非零非二次剩余的数量也恰为 \(\frac{p-1}{2}\) 个。

  2. \(a^{\frac{p-1}{2}}\equiv 1\Longleftrightarrow n\) 是二次剩余

假如我们要找 \(n\) 的二次剩余，那么我们随机检验找到一个 \(a\) 使得 \(a^2-n\) 是非二次剩余。类比于虚数单位，定义 \(i^2\equiv a^2-n\)，随后有结论：

\(\pm(a+i)^{\frac{p+1}{2}}\) 是 \(n\) 的二次剩余。

证明：\((a+i)^{p+1}\equiv(a+i)(a^p+i^p)\equiv(a+i)(a-i)\equiv n\)。

P15649

设 \(dp_{i,j}\) 表示点 \(i\) 向下延申重链长度为 \(j\) 的概率，枚举儿子及其重链长度，会发现这就是背包转移，每次统计节点答案需要可撤销背包，也就是多项式除法，最低位不一定非 \(0\) 那就平移一下。

P3307

第一步自然是莫反，

\[\sum_{i=1}^a\sum_{j=i}^a\sum_{k=j}^a=\sum_{d=1}^{a}\mu(d)\frac{\lfloor\frac{a}{d}\rfloor(\lfloor\frac{a}{d}\rfloor+1)(\lfloor\frac{a}{d}\rfloor+2)}{6} \]

P9537

P7843

P17570

P11428

P11406

神秘卡空题，考虑十六进制倍增即可。

P17570

QOJ964

神仙题。转化为 \(\max\{i\mid\sum_{j=l}^r[a_j\le i]>i\}\)，这属于“不好维护答案但容易检验”的查询，可以考虑两种方式：整体二分和按序检验答案，这里考虑后一种。注意到对于 \(l\le l_1\le r_1\le r\)，有 \(ans_{l_1,r_1}\le ans_{l,r}\)，于是考虑从大到小扫答案，维护极大无包含区间集合。实现时使用线段树维护，询问按 \(r\) 挂在树上，用栈维护，栈顶 \(l\) 最小，同时维护 set 用来求当前活跃询问的前驱后继，删除后不断找出 \(r\in(r_1,r_2)\) 内左端点最小中右端点最大的加入。