P14360 [CSP-J 2025] 多边形

题目描述

给定 $n$ 根小木棍，第 $i$ 根的长度为 $a_i$。

你需要从中选出至少 $3$ 根木棍，并将它们首尾相接拼成一个多边形。要求多边形任意相邻两边长度之和严格大于第三边（即满足三角形不等式）。

求有多少种不同的选法（选出的木棍集合不同即为不同方案）。

输入格式

第一行一个正整数 $n$ 表示木棍数量。

第二行 $n$ 个正整数 $a_1, a_2, \ldots, a_n$ 表示每根木棍的长度。

输出格式

输出一个整数表示方案数，对 $998244353$ 取模。

样例

样例输入 #1

3
1 2 3

样例输出 #1

0

数据范围

• $3 \leq n \leq 5000$
• $1 \leq a_i \leq 5000$

提示

标签: 排序, 01背包, 动态规划

难度: 普及/提高−

来源: CSP-J 2025