hdu2021多校2

发表于 2021-07-23 分类于 hdu ，多校

竟然排到了第12名，学弟们都是神仙啊。

签到题，对于边长为 $i$ 的点，答案为 $8(n-i)^3$。

求个和即可。

简单题，树剖后转换为区间加二次函数，线段树维护即可。

也就是多校1的某两题结合起来。。。

离线后将每个点，询问插进Trie里面，Trie中每个节点维护一个线段树。

询问在线段树上查询即可，合并使用线段树合并。

给定奇质数 $p$，与整数 $a(1 < a < p)$，长度为 $p-1$ 的序列 $b$ 满足 $b_i<p,b_i\equiv ai\pmod p$。

问序列 $b$ 的逆序对个数模 $2$ 的结果。

$T\le 10^5,p\in \mathbb{P},2 \le a < p < 10^{18}$。

对于一个排列，交换任意两个数后，逆序对奇偶性一定改变。

因此，只需找到最小的 $d$，满足 $a^d\equiv 1\pmod p$，这个 $d$ 显然是 $\varphi(p)=p-1$ 的约数。

之后整个 $b$ 序列就形成了 $\frac{p-1}{d}$ 个环，每个环需要交换 $d-1$ 次。

于是答案即为 $\frac{p-1}{d}(d-1)\bmod 2$。

当且仅当 $d$ 为偶数，且 $d$ 中 $2$ 的次幂与 $p-1$ 中相同时答案为 $1$。

于是只需判断 $a^{\frac{p-1}{2}}$ 在模 $p$ 意义下是否为 $1$ 即可。