A16530 | $Beautiful Patterns (Hard Version)$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

这是该问题的困难版本。不同之处在于，本题中 $n \le 2 \cdot 10^5$。只有当你解决了本问题的所有版本后，才可以进行 hack。 进入古老的“回文宫殿”后，你注意到其墙壁上有奇异的图案。图案是由 $1 \times n$ 的马赛克组成的，每块鹅卵石被涂上 $m$ 种不同的颜色之一。 任意马赛克 $s$ 的“正确度”定义为 $s$ 的所有非空回文子段的个数。该马赛克的“美丽值”被定义为其正确度的平方。例如，对于马赛克 rgrb，有五个回文子段：r、g、r、b 和 rgr。其正确度为 $5$，美丽值为 $25$。 在宫殿内游览时，你想知道：如果每个位置上的鹅卵石颜色均独立等概率地从 $m$ 种颜色中选择，这个马赛克美丽值的期望是多少？请输出该期望对质数 $p$ 取模后的结果。

每组测试包含多组数据。第一行输入测试用例数 $t$（$1 \le t \le 1000$）。接下来的 $t$ 行，每行包含 3 个整数 $n$、$m$ 和 $p$（$1 \leq n \leq 2 \cdot 10^5$；$1 \leq m \leq 10^7$；$m < p < 10^9$），分别表示马赛克长度、可选颜色数和需要计算答案取模的质数。 保证 $p$ 是质数，且所有测试用例中 $n$ 的总和不超过 $10^6$。

每组数据输出一行，表示该马赛克美丽值的期望对 $p$ 取模后的结果。 形式化地，设 $x = p$，可以证明最终答案可表示为最简分数 $\frac{y}{z}$，其中 $y$ 与 $z$ 为整数且 $z \not \equiv 0 \pmod{x}$。请输出一个 $0 \le t < x$，满足 $t \cdot z \equiv y \pmod{x}$。

输入 #1

3
2 2 101
5 1 999999937
100 23190 3214373

输出 #1

57
225
2347147

C++ 编辑器

输入

输出