2020-2021:teams:hotpot:agc047
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:hotpot:agc047 [2020/08/14 12:51] lotk |
2020-2021:teams:hotpot:agc047 [2020/08/14 12:55] (当前版本) lotk |
||
|---|---|---|---|
| 行 41: | 行 41: | ||
| 经过分析之后，我们可以发现一些性质，即长串一定由短串组成，且从短串的第二位开始必然是连续的一段，利用这个性质，我们对串从短到长排序之后，每次对字母做一个桶，在trie树上寻找是否有统计过的点并累加答案，之后倒序插入一个trie树中（只插入到第二位，每次对第一位的个数进行统计）。 | 经过分析之后，我们可以发现一些性质，即长串一定由短串组成，且从短串的第二位开始必然是连续的一段，利用这个性质，我们对串从短到长排序之后，每次对字母做一个桶，在trie树上寻找是否有统计过的点并累加答案，之后倒序插入一个trie树中（只插入到第二位，每次对第一位的个数进行统计）。 | ||
| - | =====C - ===== | + | =====C - Product Modulo===== |
| ====题目大意==== | ====题目大意==== | ||
| + | |||
| + | 给定n个数，求$\sum_{1\le i<j\le n}(a_i\times a_j\%200003)$ | ||
| ====数据范围==== | ====数据范围==== | ||
| + | |||
| + | $1\le n\le 200000$ | ||
| ====解题思路==== | ====解题思路==== | ||
| + | |||
| + | 2是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 - ===== | =====D - ===== | ||
2020-2021/teams/hotpot/agc047.1597380683.txt.gz · 最后更改: 2020/08/14 12:51 由 lotk
