分数: 600 点
问题陈述
你被给予 M 整数三元组 (L_i,R_i,S_i).
考虑元组 A=(A_1,A_2,\ldots,A_N) of N 积极 满足以下所有条件的整数。
- 总和 A_{L_i}, A_{L_i+1}, \ldots, A_{R_i} is S_i.
如果有无穷多个满足条件的元组,则输出 Infinity;否则,输出此类元组的数量,模 998244353.
约束
- 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) 是不同的。
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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
我们有以下两个条件。
- A_1+A_2=7
- A_2+A_3=10
六元组 A=(1,6,4), (2,5,5), (3,4,6), (4,3,7), (5,2,8), (6,1,9) 满足条件,所以输出 6 模数 998244353,即输出 6.
示例输入 2
2 1 1 1 10
示例输出 2
Infinity
有无限多个元组 A 满足条件。
示例输入 3
2 2 1 1 10 1 2 1
示例输出 3
0
没有元组 A 满足条件。