2025 T4 多边形

主知识点：动态规划。交叉标签：动态规划、01背包、计数、枚举、深搜。
暴力标注：DP 可用暴力拿部分分。
OJ 使用标准输入与标准输出。原比赛文件名为 polygon.in / polygon.out；下方如保留原文件约定，以本句的 OJ 约定为准。
时限 1 秒；内存 512 MiB；测试点 25；总分 100。
数据来源：自制训练数据（90 点中的本题部分，非官方）。

2025 年本题评测数据为自制训练数据；下方约束表仍是原题约束。训练分数不等同于原赛成绩。

题目描述

有 $n$ 根带下标的木棍，第 $i$ 根长度为 $a_i$。选择若干根后能组成多边形，当且仅当选择数 $m\ge3$，并且：

$$\sum_{j=1}^m l_j>2\max_{1\le j\le m}l_j.$$

统计可组成多边形的选择方案数，答案模 998244353。方案按所选下标集合区分；同长度的不同木棍仍是不同物品。

输入格式

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

输入的第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$，表示小 R 的小木棍的长度。

输出格式

输出一行一个非负整数，表示小 R 选出的小木棍能够拼成一个多边形的方案数对 $998,244,353$ 取模后的结果。

样例

样例 1

输入：

5
1 2 3 4 5

输出：

9

样例 2

输入：

5
2 2 3 8 10

输出：

6

数据范围与特殊性质

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

• $3 \leq n \leq 5\,000$;

• 对于所有 $1 \leq i \leq n$，均有 $1 \leq a_i \leq 5\,000$。

测试点编号	$n \leq$	$\max_{i=1}^{n} a_i \leq$
$1 \sim 3$	$3$	$10$
$4 \sim 6$	$10$	$10^2$
$7 \sim 10$	$20$
$11 \sim 14$	$500$
$15 \sim 17$		$1$
$18 \sim 20$	$5\,000$
$21 \sim 25$		$5\,000$

附加样例

本题的公开样例整理在对应的“样例”ZIP 中。样例不计入评测测试点；题面中的样例也已保留。

暴力退路标注（教学补充）

DP 可用暴力拿部分分。枚举下标子集（DFS 或位掩码），维护数量、总长、最大长，判断数量≥3 且 sum>2max。n≤20 的 1~10 点占 40%；增量维护可将统计降到 O(2^n)。a_i=1 的 15~20 点另用 2^n-1-n-C(n,2) 可得 24%，与前 40% 合计 64%。

目标范围：40% 子集枚举；加全 1 特判可争取 64%。部分分按原题规模判断，不构成对任意实现或评测机的得分保证。

来源与整理说明

题目原作者/发布者：中国计算机学会 CCF / NOI。题意经过改写，保留公式、输入输出、样例及约束；知识点和暴力标注为本次整理补充。

• 题面及约束校对来源：洛谷 CCF_NOI 题目 P14360
• 赛事：CSP-J 第二轮入门级 2025。
• 详细数据来源、版本和哈希见总包 来源与校验/manifest.json。