← 返回题目列表

AtCoder · abc466_g

G. 段总和约束

中文机器翻译题面 查看原题

分数: 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 满足条件。