多边形（polygon）

本题为 CSP-J 2025 第二轮真题。本 OJ 采用标准输入输出评测，无需文件重定向。

【题目描述】 小R 喜欢玩小木棍。小R 有n 根小木棍，第i (1 ≤i ≤n) 根小木棍的长度为ai。 小X 希望小R 从这n 根小木棍中选出若干根小木棍，将它们按任意顺序首尾相连 拼成一个多边形。小R 并不知道小木棍能拼成多边形的条件，于是小X 直接将条件告 诉了他：对于长度分别为l1, l2, . . . , lm 的m 根小木棍，这m 根小木棍能拼成一个多边 形当且仅当m ≥3 且所有小木棍的长度之和.大.于所有小木棍的长度最大值的两倍，即 ∑m i=1 li > 2 × maxm i=1 li。 由于小R 知道了小木棍能拼成多边形的条件，小X 提出了一个更难的问题：有多 少种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形？你需要帮助小R 求 出选出的小木棍能够拼成一个多边形的方案数。两种方案不同当且仅当选择的小木棍的 .下.标.集.合.不.同，即存在1 ≤i ≤n，使得其中一种方案选择了第i 根小木棍，但另一种方 案未选择。由于答案可能较大，你只需要求出答案对998, 244, 353 取模后的结果。 【输入格式】 从文件polygon.in 中读入数据。 输入的第一行包含一个正整数n，表示小R 的小木棍的数量。 输入的第二行包含n 个正整数a1, a2, . . . , an，表示小R 的小木棍的长度。 【输出格式】 输出到文件polygon.out 中。 输出一行一个非负整数，表示小R 选出的小木棍能够拼成一个多边形的方案数对 998, 244, 353 取模后的结果。 【样例1 输入】 1 5 2 1 2 3 4 5 【样例1 输出】 1 9 【样例1 解释】 共有以下9 种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形：

1. 选择第2, 3, 4 根小木棍，长度之和为2 + 3 + 4 = 9，长度最大值为4；
2. 选择第2, 4, 5 根小木棍，长度之和为2 + 4 + 5 = 11，长度最大值为5；
3. 选择第3, 4, 5 根小木棍，长度之和为3 + 4 + 5 = 12，长度最大值为5；
4. 选择第1, 2, 3, 4 根小木棍，长度之和为1 + 2 + 3 + 4 = 10，长度最大值为4；
5. 选择第1, 2, 3, 5 根小木棍，长度之和为1 + 2 + 3 + 5 = 11，长度最大值为5；
6. 选择第1, 2, 4, 5 根小木棍，长度之和为1 + 2 + 4 + 5 = 12，长度最大值为5；
7. 选择第1, 3, 4, 5 根小木棍，长度之和为1 + 3 + 4 + 5 = 13，长度最大值为5；
8. 选择第2, 3, 4, 5 根小木棍，长度之和为2 + 3 + 4 + 5 = 14，长度最大值为5；
9. 选择第1, 2, 3, 4, 5 根小木棍，长度之和为1 + 2 + 3 + 4 + 5 = 15，长度最大值为5。 【样例2 输入】 1 5 2 2 2 3 8 10 【样例2 输出】 1 6 共有以下6 种选择小木棍的方案，使得选出的小木棍能够拼成一个多边形：
10. 选择第1, 2, 3 根小木棍，长度之和为2 + 2 + 3 = 7，长度最大值为3；
11. 选择第3, 4, 5 根小木棍，长度之和为3 + 8 + 10 = 21，长度最大值为10；
12. 选择第1, 2, 4, 5 根小木棍，长度之和为2 + 2 + 8 + 10 = 22，长度最大值为10；
13. 选择第1, 3, 4, 5 根小木棍，长度之和为2 + 3 + 8 + 10 = 23，长度最大值为10；
14. 选择第2, 3, 4, 5 根小木棍，长度之和为2 + 3 + 8 + 10 = 23，长度最大值为10；
15. 选择第1, 2, 3, 4, 5 根小木棍，长度之和为2 + 2 + 3 + 8 + 10 = 25，长度最大值为 10。 【样例3】 见选手目录下的polygon/polygon3.in 与polygon/polygon3.ans。 该样例满足测试点7 ∼10 的约束条件。 【样例4】 见选手目录下的polygon/polygon4.in 与polygon/polygon4.ans。 该样例满足测试点11 ∼14 的约束条件。 【子任务】 对于所有测试数据，保证： • 3 ≤n ≤5, 000； • 对于所有1 ≤i ≤n，均有1 ≤ai ≤5, 000。 测试点编号 n ≤ maxn i=1 ai ≤ 1 ∼3 3 10 4 ∼6 10 102 7 ∼10 20 11 ∼14 500 15 ∼17 1 18 ∼20 5, 000 21 ∼25 5, 000

📦 本题含官方测试数据（CC BY-NC，noi.cn 发布），共 8 个测试点。