CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
[[http://112.74.186.118/doku.php?id=2020-2021:teams:legal_string:%E5%90%84%E5%AD%A3%E5%BA%A6%E8%AE%AD%E7%BB%83%E8%AE%A1%E5%88%92%E5%8F%8A%E8%AE%AD%E7%BB%83%E8%AE%B0%E5%BD%95|back]]

====== 2020/08/01--2020/08/07 周报 ======

===== 团队训练 =====

===== 姜一凡 =====

==== 专题 ====

[[..:半平面交]]

==== 比赛 ====

无

==== 题目 ====

无

===== 蒋贤蒙 =====

==== 专题 ====

[[..:jxm2001:动态规划_1|动态规划 1]]

[[..:jxm2001:多项式_1|多项式 1]]

[[..:jxm2001:多项式_2|多项式 2]]

==== 比赛 ====

无

==== 题目 ====

见专题部分

===== 王赵安 =====

==== 专题 ====

[[..:lgwza:普通莫队算法|普通莫队算法]]

[[..:lgwza:状压 DP|状压 DP]]

[[..:lgwza:数位 DP|数位 DP]]
==== 比赛 ====

[[https://atcoder.jp/contests/abc174|AtCoder Beginner Contest 174]] ''%%pro:5/6/6%%'' ''%%rk:1676/9750%%''
==== 题目 ====

见专题部分
===== 本周推荐 =====

==== 姜一凡 ====

[[https://www.luogu.com.cn/problem/P4196|洛谷]]

=== 标签 ===

半平面交

=== 题意 ===

求给定多边形的交

=== 题解 ===

把每个多边形表示成半平面交的形式，然后只需计算所有的半平面交。

==== 蒋贤蒙 ====

[[https://www.luogu.com.cn/problem/P3321|洛谷p3321]]

=== 标签 ===

数论，原根，$\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}$ 经典题。

==== 王赵安 ====

[[https://atcoder.jp/contests/abc174/tasks/abc174_f|AtCoder Beginner Contest 174 F - Range Set Query]]

=== 标签 ===

普通莫队算法

=== 题意 ===

$N$ 个数，$Q$ 次询问，每次询问给出一个区间，求该区间内不相同的数的个数

=== 题解 ===

采用普通莫队算法。先将整个 $1\sim N$ 的区间分成 $\sqrt N$ 块，然后将 $Q$ 个询问区间按下列规则排序：以 $l$ 所在块为第一关键字从小到大排序，若 $l$ 在同一块，若是在第奇数块，则以 $r$ 作为第二关键字从小到大排，若是在第偶数块，则以 $r$ 作为第二关键字从大到小排。这样将 $Q$ 个询问区间经过排序后，能以较小的代价进行区间转移。区间长度每次增加 $1$ 或减少 $1$ 时能维护答案。

=== 评价 ===

普通莫队算法模板题
CVBB ACM Team

用户工具

站点工具

页面工具
