目录
2020/08/01--2020/08/07 周报
团队训练
姜一凡
专题
比赛
无
题目
无
蒋贤蒙
专题
比赛
无
题目
见专题部分
王赵安
专题
比赛
AtCoder Beginner Contest 174 pro:5/6/6 rk:1676/9750
题目
见专题部分
本周推荐
姜一凡
标签
半平面交
题意
求给定多边形的交
题解
把每个多边形表示成半平面交的形式，然后只需计算所有的半平面交。
蒋贤蒙
标签
数论，原根，$\text{NTT}$
题意
给定一个集合 $S$，问从集合 $S$ 中依次选出 $n$ 个数乘积模 $p$ 意义下恰好为 $x$ 的方案数。
数据保证 $p\le 8000,n\le 10^9,1\le x\lt p$，且 $p$ 为素数，最后答案对 $1004535809$ 取模。
题解
先考虑将乘法转化为加法。素数 $p$ 一定有原根 $g$，考虑将 $S$ 中的每个数表示为 $p$ 的幂次，且 $x=g^y$。
于是合法方案转化为幂次和模 $p-1$ 意义下恰好为 $y$ 的方案。
令 $f_{i,j}$ 表示依次选择 $i$ 个数幂次和恰好为 $j$ 的方案，于是有递推式 $f_{i,j}=\sum_{k=0}^j f_{i-1,j-k}f_{1,k}$。
考虑 $\text{NTT}$ 加速卷积过程。由于只关注模 $p-1$ 意义的和，于是可以将每次卷积后大于 $p-1$ 的项转移到取模后的结果中。
于是得到一个暴力递推算法，时间复杂度为 $O(np\log p)$。
考虑快速幂优化递推过程，于是时间复杂度降为 $O(p\log p\log n)$。
评价
$\text{NTT}$ 经典题。
王赵安
标签
普通莫队算法
题意
$N$ 个数，$Q$ 次询问，每次询问给出一个区间，求该区间内不相同的数的个数
题解
采用普通莫队算法。先将整个 $1\sim N$ 的区间分成 $\sqrt N$ 块，然后将 $Q$ 个询问区间按下列规则排序：以 $l$ 所在块为第一关键字从小到大排序，若 $l$ 在同一块，若是在第奇数块，则以 $r$ 作为第二关键字从小到大排，若是在第偶数块，则以 $r$ 作为第二关键字从大到小排。这样将 $Q$ 个询问区间经过排序后，能以较小的代价进行区间转移。区间长度每次增加 $1$ 或减少 $1$ 时能维护答案。
评价
普通莫队算法模板题
