AGC 047 题解

A

---

容易想到乘上 1e9，那么意味着相乘得到的数是 1e18 的倍数。即因子中 2 和 5 的个数都 >= 18，开个桶随便做一下。【注意读入，我没用字符串就 wa 了 qvq 没试过 long double 不知道行不行

B

---

容易发现若 T 能和 S 匹配，把 T 第一个字符去掉以后就是 S 的一个后缀。

题目只给出了总串长！这启发我们想到结合 Trie 树等结构实现一个 O(n) 的算法。

C

---

对多项式大师来说是套路题，对我来说。。qvq

容易想到枚举模后乘积。

$$F(x) = \sum [a_i == x]$$ $$ans = \sum\limits_d d \sum_{(xy\bmod P == d)}F(x)F(y)$$

我们想到了卷积，但这还不是卷积形式，于是再化一步：

$$F(x) = \sum [g^{a_i} == x]$$

其中 g 是 P 的原根之一

$$ans = \sum\limits_d g^d \sum_{((x + y)\bmod P == d)}F(x)F(y)$$

那这就是个循环卷积啦。

关于原根：原根的定义和性质：对于任何 $0$ ~ $P - 1$ 中的数 $i$、$j$($i \neq j$), 有 $g^i \neq g^j(\bmod P)$，即 $g^i$ 在 mod P 意义下可以取遍 $0$ ~ $P - 1$ 所有数。

关于找原根：原根很小，一般在 100 以内，枚举，若存在 P 的因子 x 使得 $g^{\frac{P - 1}{x}} \equiv 1 (\bmod P)$ 那么 g 就不是原根。否则就是。

D

---

咕咕

E

---

咕咕

F

---

咕咕