← 返回题目列表

AtCoder · ndpc2026_r

R. 三元组

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

分数: 7 点

问题陈述

对于非负整数 u, v,我们写 u \subseteq v 的意思是 u\ \mathrm{OR}\ v = v。在这里, \mathrm{OR} 表示按位或运算。

非负整数三元组序列 ((u_1,v_1,w_1),(u_2,v_2,w_2),\dots,(u_k,v_k,w_k)) 被称为 好的序列 如果满足以下所有条件:

  • k \geq 2.
  • 对于所有整数 i 这样 1 \leq i \leq k-1,它认为 u_i \subseteq w_{i+1} \subseteq v_i.

给你一个三元组序列 A = ((x_1,y_1,z_1), (x_2,y_2,z_2), \dots, (x_N,y_N,z_N)).
对于所有人 i 这样 1 \leq i \leq N,它认为 x_i \subseteq y_i.

有 2^N - N - 1 的子序列 A 长度至少 2 (分别统计不同的指数选择)。
其中,求好序列的个数,取模 998244353.

约束

  • 2 \leq N \leq 3 \times 10^5
  • 0 \leq x_i < 2^{24}
  • 0 \leq y_i < 2^{24}
  • 0 \leq z_i < 2^{24}
  • x_i \ \mathrm{OR}\ y_i = y_i
  • 所有输入值均为整数

部分分数

此题得分不全。

  • 如果您求解数据集,其中 \max(x_i, y_i, z_i) < 2^{18} 对于每个整数都成立 i 这样 1 \leq i \leq N,你会得到 4 点。

输入

输入由标准输入给出,格式如下:

N
x_1 y_1 z_1
x_2 y_2 z_2
\vdots
x_N y_N z_N

输出

打印作为子序列的好序列的数量 A 长度至少 2,模数 998244353.


示例输入 1

3
2 6 3
0 7 4
1 5 2

示例输出 1

2

有 2 满足条件的序列:

  • ((2,6,3),(1,5,2))
  • ((0,7,4),(1,5,2))

示例输入 2

8
0 9 5
0 16 3
0 8 4
0 5 23
0 20 29
0 12 26
0 6 0
0 19 8

示例输出 2

9

示例输入 3

13
0 16777215 14827221
8390656 12582911 5535137
4325888 16711679 2641072
8849409 16776703 15212885
8389632 16514814 9612654
0 12517373 13419138
0 16777215 5271292
14464 16236535 6997452
131072 15727483 10218943
16 16646111 15524257
1181961 14647295 5595336
8388768 16775147 5472548
0 16777215 297940

示例输出 3

34