无

yukicoder contest 260 (Typical Game Contest)

比较有做的价值的专题场，全都是玩游戏。部分题目解析 见此。

AtCoder Grand Contest 047

比赛名称

比赛名称

AGC 047 C - Product Modulo

• 题意：已知 $P = 200\ 003$ 是质数。给 $n \leq 2 \times 10^5$ 的数列 $a_1, a_2, \ldots, a_n$，值域在 $[0, P)$，求 $\sum _{i=1}^n \sum _{j = i+1}^n (a_i \cdot a_j \bmod P)$。注意结果不需要对 $P$ 取模。
• 题解：
  • 如果存在一种卷积操作使得 $[x^n]H(x) = \sum _{i \cdot j = n} [x^i]F(x) \cdot [x^j]G(x)$，那么上面的问题就可以把每个数出现次数的多项式直接卷积做了。可以发现对数性质满足 $\log a + \log b = \log ab$，如果能将指数部分先映射到对数，普通卷积完再还原回来，那么就能实现上述卷积。
  • 经过测试发现 $2$ 是 $P$ 的一个原根，因此可以用 $\log_2(x)$ 进行映射。由于是指数上的运算，原根的循环节是 $\varphi(P) = P - 1$ 而不是 $P$，故做完多项式之后指数超出 $P - 1$ 的部分应当模一下 $P - 1$。
  • 系数并不是很大，直接 FFT 精度也是足够的。
• 备注：利用原根性质操作的妙妙题，即使赛场上想出来了也还是觉得很妙。

题目名称

• 题意：
• 题解：
• 备注：

题目名称

• 题意：
• 题解：
• 备注：