• 文件输入：prime.in
• 文件输出：prime.out
• 时间限制：3s
• 空间限制：512MB

题目描述

给定长度为 $n$ 的整数数组 $a = [a_1, a_2, \ldots, a_n]$。对于 $a$ 的任意非空子序列 $b$，可以执行以下操作任意次（包括零次）：

1. 选择一个质数 $p$；
2. 将 $b$ 中所有当前值能被 $p$ 整除的元素同时减 $1$，其余元素保持不变。

令 $f(b)$ 为最大的整数 $x$，使得存在某个操作序列，执行后 $b$ 中所有元素均等于 $x$。

求所有非空子序列 $b$ 的 $f(b)$ 之和，对 $998\,244\,353$ 取模：

$$\sum_{\substack{b \subseteq a \\ b \neq \varnothing}} f(b) \pmod{998\,244\,353}.$$

子序列按所选下标区分，即使元素值相同。每个子序列独立考虑，初始值取原数组中的对应值。

子序列定义： 若序列 $a$ 可由序列 $b$ 删除若干（可能为零个或全部）任意位置的元素得到，则称 $a$ 是 $b$ 的子序列。

输入格式

每个测试包含多个测试用例。第一行包含测试用例数 $t$。

每个测试用例的第一行包含一个整数 $n$ ——数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ ——数组 $a$ 的元素。

输出格式

对于每个测试用例，输出一个整数——所有非空子序列 $b$ 的 $f(b)$ 之和，对 $998\,244\,353$ 取模。

样例

4
1
1
4
2 4 4 4
4
2 3 4 4
6
3 6 1 1 1 1

1
37
34
72

说明/提示

样例解释

第一个测试用例中，唯一的非空子序列是 $[1]$，无需操作，贡献为 $f([1])=1$。

第二个测试用例中，$2^3-1=7$ 个仅由值 $4$ 构成的非空子序列贡献 $4 \cdot 7 = 28$。子序列 $[2]$ 贡献 $2$。每个同时包含值 $2$ 和至少一个值 $4$ 的 $7$ 个子序列均有 $f(b)=1$。因此答案为 $28+2+7=37$。

数据规模与约定

对于所有的数据，$1 \le t \le 10^4$，$1 \le n \le 300\,000$，$1 \le a_i \le n$，保证所有测试用例中 $n$ 的总和不超过 $300\,000$。

子任务编号	分值	数据范围	特殊性质
$1$	$10$	$t \le 10, n \le 10$	无
$2$		$t,n \le 3000$，所有测试用例的 $n$ 总和不超过 $3000$	A
$3$	$15$		无
	$10$	和所有数据的数据范围一样	A
$4$	$55$		无

对于子任务 $i(i \gt 1)$，你需要答对所有编号 $\lt i$ 的子任务才能获得子任务 $i$ 的得分。

特殊性质 A：对于所有 $1 \le i \le n$，均有 $a_i \le \min(n, 10)$。

测试样例

一共 $5$ 组测试样例。

$prime\texttt{i}.in$ 和 $prime\texttt{i}.ans$ 对应子任务 $i$。

点击下载 测试样例