2020-2021:teams:hotpot:agc047

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:hotpot:agc047 [2020/08/14 12:27]
misakatao 创建
+++ 2020-2021:teams:hotpot:agc047 [2020/08/14 12:55] (当前版本)
lotk
@@ 行 1: / 行 1: @@
-（占位用）
+======Atcoder Grand Contest 047======
+[[https://atcoder.jp/contests/agc047/tasks|比赛链接]]
+=====A -  Integer Product=====
+====题目大意====
+给出 $n$ 个实数 $A_i$，问有多少两两相乘得到整数
+====数据范围====
+ $2 \le n \le 200000$
+ $0 < A_i < 1e4 $
+ps: $A_i$ 小数位后最多有9位
+====解题思路====
+我们不妨将 $A_i$ 都乘以 $1e9$, 然后对其质因数分解统计 2 和 5 的个数（初始显然是 -9），之后排序扫描一维树状数组统计一维计算答案即可。
+=====B -  First Second=====
+====题目大意====
+给出 $n$ 个字符串 $S_i$，给出一种操作方式，即每次第一个和第二个选一个删除，问有多少串能够转换成另外一个串，统计对数。
+====数据范围====
+$ 2 \le n \le 2e5$
+$ S_i \ne S_j$
+$ |S_1+S_2...+S_n| \le 1e6$
+ps: 串全由小写字母组成
+====解题思路====
+经过分析之后，我们可以发现一些性质，即长串一定由短串组成，且从短串的第二位开始必然是连续的一段，利用这个性质，我们对串从短到长排序之后，每次对字母做一个桶，在trie树上寻找是否有统计过的点并累加答案，之后倒序插入一个trie树中（只插入到第二位，每次对第一位的个数进行统计）。
+=====C - Product Modulo=====
+====题目大意====
+给定n个数，求$\sum_{1\le i<j\le n}(a_i\times a_j\%200003)$
+====数据范围====
+$1\le n\le 200000$
+====解题思路====
+是200003的原根。将$a_i$转成$2^k_i$，满足$2^k\equiv a_i \pmod {200003}，k\le 200001$。用fft计算多项式f(x)的平方，其中f(x)的i次项系数为$2^i$的个数。再遍历统计一遍即可。
+=====D - =====
+====题目大意====
+====数据范围====
+====解题思路====
+=====E - =====
+====题目大意====
+====数据范围====
+====解题思路====
+=====F - =====
+====题目大意====
+====数据范围====
+====解题思路====

2020-2021/teams/hotpot/agc047.1597379256.txt.gz · 最后更改: 2020/08/14 12:27 由 misakatao