问题 D: [CSP-J 2025] 多边形

内存限制：512 MB 时间限制：1.000 S

评测方式：文本比较命题人：

提交：8 解决：3

小 R 喜欢玩小木棍。小 R 有 $n$ 根小木棍，第 $i$ ( $1 \leq i \leq n$ ) 根小木棍的长度为 $a_{i}$ 。

小 X 希望小 R 从这 $n$ 根小木棍中选出若干根小木棍，将它们按任意顺序首尾相连拼成一个多边形。小 R 并不知道小木棍能拼成多边形的条件，于是小 X 直接将条件告诉了他：对于长度分别为 $l_{1}, l_{2}, \dots, l_{m}$ 的 $m$ 根小木棍，这 $m$ 根小木棍能拼成一个多边形当且仅当 $m \geq 3$ 且所有小木棍的长度之和大于所有小木棍的长度最大值的两倍，即 $\sum_{i = 1}^{m} l_{i} > 2 \times max_{i = 1}^{m} l_{i}$ 。

由于小 R 知道了小木棍能拼成多边形的条件，小 X 提出了一个更难的问题：有多少种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形？你需要帮助小 R 求出选出的小木棍能够拼成一个多边形的方案数。两种方案不同当且仅当选择的小木棍的下标集合不同，即存在 $1 \leq i \leq n$ ，使得其中一种方案选择了第 $i$ 根小木棍，但另一种方案未选择。由于答案可能较大，你只需要求出答案对 $998, 244, 353$ 取模后的结果。

说明/提示

【样例 1 解释】

共有以下 $9$ 种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形：

选择第 $2, 3, 4$ 根小木棍，长度之和为 $2 + 3 + 4 = 9$ ，长度最大值为 $4$ ;
选择第 $2, 4, 5$ 根小木棍，长度之和为 $2 + 4 + 5 = 11$ ，长度最大值为 $5$ ;
选择第 $3, 4, 5$ 根小木棍，长度之和为 $3 + 4 + 5 = 12$ ，长度最大值为 $5$ ;
选择第 $1, 2, 3, 4$ 根小木棍，长度之和为 $1 + 2 + 3 + 4 = 10$ ，长度最大值为 $4$ ;
选择第 $1, 2, 3, 5$ 根小木棍，长度之和为 $1 + 2 + 3 + 5 = 11$ ，长度最大值为 $5$ ;
选择第 $1, 2, 4, 5$ 根小木棍，长度之和为 $1 + 2 + 4 + 5 = 12$ ，长度最大值为 $5$ ;
选择第 $1, 3, 4, 5$ 根小木棍，长度之和为 $1 + 3 + 4 + 5 = 13$ ，长度最大值为 $5$ ;
选择第 $2, 3, 4, 5$ 根小木棍，长度之和为 $2 + 3 + 4 + 5 = 14$ ，长度最大值为 $5$ ;
选择第 $1, 2, 3, 4, 5$ 根小木棍，长度之和为 $1 + 2 + 3 + 4 + 5 = 15$ ，长度最大值为 $5$ 。

【样例 2 解释】

共有以下 $6$ 种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形：

选择第 $1, 2, 3$ 根小木棍，长度之和为 $2 + 2 + 3 = 7$ ，长度最大值为 $3$ ;
选择第 $3, 4, 5$ 根小木棍，长度之和为 $3 + 8 + 10 = 21$ ，长度最大值为 $10$ ;
选择第 $1, 2, 4, 5$ 根小木棍，长度之和为 $2 + 2 + 8 + 10 = 22$ ，长度最大值为 $10$ ;
选择第 $1, 3, 4, 5$ 根小木棍，长度之和为 $2 + 3 + 8 + 10 = 23$ ，长度最大值为 $10$ ;
选择第 $2, 3, 4, 5$ 根小木棍，长度之和为 $2 + 3 + 8 + 10 = 23$ ，长度最大值为 $10$ ;
选择第 $1, 2, 3, 4, 5$ 根小木棍，长度之和为 $2 + 2 + 3 + 8 + 10 = 25$ ，长度最大值为 $10$ 。

【子任务】

对于所有测试数据，保证：

$3 \leq n \leq 5000$ ;
对于所有 $1 \leq i \leq n$ ，均有 $1 \leq a_{i} \leq 5000$ 。

输入的第一行包含一个正整数 $n$ ，表示小 R 的小木棍的数量。

输入的第二行包含 $n$ 个正整数 $a_{1}, a_{2}, \dots, a_{n}$ ，表示小 R 的小木棍的长度。

输出一行一个非负整数，表示小 R 选出的小木棍能够拼成一个多边形的方案数对

998, 244, 353

取模后的结果。

样例输入1：
5
1 2 3 4 5

样例输出1：
9

样例输入2：
5
2 2 3 8 10
样例输出2：
6

问题 D: [CSP-J 2025] 多边形

题目描述

说明/提示

【样例 1 解释】

【样例 2 解释】

【子任务】

输入

输出

样例输入复制

问题 D: [CSP-J 2025] 多边形

题目描述

说明/提示

【样例 1 解释】

【样例 2 解释】

【子任务】

输入

输出

样例输入 复制

样例输入复制