区间和约束(Segment Sum Constraints)

题目描述

给定 $M$ 个三元组 $(L_i, R_i, S_i)$。

考虑满足以下所有条件的、由 $N$ 个正整数组成的序列 $A$：

$$A_{L_i} + A_{L_i+1} + \ldots + A_{R_i} = S_i \quad (i = 1, 2, \ldots, M)$$

如果这样的序列有无穷多个，输出 Infinity；否则，输出满足条件的序列个数对 $998244353$ 取模的结果。

输入格式

输入从标准输入按以下格式给出：

N M
L_1 R_1 S_1
L_2 R_2 S_2
\vdots
L_M R_M S_M

输出格式

如果满足条件的序列有无穷多个，输出 Infinity；否则输出序列个数对 $998244353$ 取模的结果。

样例输入 #1

3 2
1 2 7
2 3 10

样例输出 #1

6

满足条件的序列有 $(1,6,4), (2,5,5), (3,4,6), (4,3,7), (5,2,8), (6,1,9)$ 共 $6$ 个。

样例输入 #2

2 1
1 1 10

样例输出 #2

Infinity

约束为 $A_1 = 10$，$A_2$ 可以是任意正整数，因此有无穷多个满足条件的序列。

样例输入 #3

2 2
1 1 10
1 2 1

样例输出 #3

0

由 $A_1 = 10$ 和 $A_1 + A_2 = 1$ 得 $A_2 = -9$，不是正整数，因此没有满足条件的序列。

数据范围

• $1 \leq N \leq 8$
• $1 \leq M \leq 36$
• $1 \leq L_i \leq R_i \leq N$
• $1 \leq S_i \leq 10^9$
• 所有 $(L_i, R_i)$ 互不相同
• 所有输入值为整数

知识点与难度

本题涉及的知识点从属于 GESP 五级，难度等级：⭐⭐⭐⭐。

---

测试点分布

Subtask	分值	测试点编号	说明
0	10	1~2	样例
1	20	3~8	小规模 N≤4, M≤6 / 特殊: N=1 / 特殊: M=1
2	15	9~11	Hack: 无解 / Hack: 唯一解 / Hack: Infinity
3	30	12~20	中规模 N≤6, M≤15 / 大规模 N=8, M=36
4	25	21~25	随机 N≤8, M≤36 回归