分数: 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