#P17975. [AMPPZ 2025]Count Triangular Sequences
[AMPPZ 2025]Count Triangular Sequences
Count Triangular Sequences
时间限制:1 秒。空间限制:1024 MiB。
题目描述
给定整数 。一个整数序列称为“三角形序列”,当且仅当它满足以下条件:
- 序列长度不超过 ;
- 每个元素均在 内;
- 可以选出三个不同位置,使这三个位置上的数能作为一个非退化三角形的三条边长。
非退化三角形的面积必须为正,即最大边长严格小于另两条边长之和。
求三角形序列的数量,对 取模。序列有顺序,改变元素顺序可能得到不同序列;元素允许重复。
输入格式
一行一个整数 。
输出格式
一行一个整数,表示答案对 取模的结果。
数据范围
。
样例 1
输入
3
输出
15
样例 2
输入
4
输出
254
说明
例如,当 时, 是合法序列, 也合法,因为可以选择边长 。
不合法,因为无论选择哪三个位置,都不能组成非退化三角形。 也不合法,因为长度不足三。