P9135 [THUPC 2023 初赛] 快速 LCM 变换

题目描述

小 I 今天学习了快速最小公倍数变换(Fast Least-Common-Multiple Transform, FLT),于是他想考考你。 给定一个长度为 $n$ 的正整数序列 $r_1,r_2,\cdots,r_n$。你需要做以下操作恰好一次: - 选择整数 $i,j$ 使得 $1 \le i < j \le n$。在序列末尾加入 $(r_i+r_j)$,并将 $r_i$ 和 $r_j$ 从序列中删除。 可以注意到总共有 $\frac{n(n-1)}{2}$ 种可能的操作,每种操作会得到一个长度为 $n-1$ 的序列。 你需要对所有的这 $\frac{n(n-1)}{2}$ 个序列,求出序列中所有元素的最小公倍数,并给出它们的和模 $998244353$ 的值。

输入格式

输出格式

说明/提示

#### 样例解释 1 - $i=1,j=2$ 时,得到的序列为 $\{4,5\}$,最小公倍数为 $20$; - $i=1,j=3$ 时,得到的序列为 $\{3,6\}$,最小公倍数为 $6$; - $i=2,j=3$ 时,得到的序列为 $\{2,7\}$,最小公倍数为 $14$。 因此输出为 $20+6+14=40$。 #### 子任务 对于所有测试数据,$2 \le n \le 5 \times 10^5, 1 \le r_1,r_2,\cdots,r_n \le 10^6$。 #### 题目来源 来自 2023 清华大学学生程序设计竞赛暨高校邀请赛(THUPC2023)初赛。 题解等资源可在 查看。