AT_ndpc2026_r 3 つ組

对于非负整数 $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$。 - 对于所有满足 $1 \leq i \leq k-1$ 的整数 $i$，都有 $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))$。 对于所有 $1 \leq i \leq N$，都有 $x_i \subseteq y_i$。 $A$ 长度至少为 $2$ 的子序列总共有 $2^N - N - 1$ 个（不同下标的选择分别计数）。 在这些子序列中，满足条件的“好序列”有多少个？请对 $998244353$ 取模输出。

从标准输入读入，格式如下： > $N\ x_1\ y_1\ z_1\ x_2\ y_2\ z_2\ \dots\ x_N\ y_N\ z_N$

输出 $A$ 的所有长至少为 $2$ 的子序列中“好序列”的数目，结果对 $998244353$ 取模。

### 部分分数 本题包含部分分数。 - 若你能解决所有 $1 \leq i \leq N$ 满足 $\max(x_i, y_i, z_i) < 2^{18}$ 的数据，可以得到 $4$ 分。 ### 样例解释 1 共有 $2$ 个序列满足条件： - $((2,6,3),(1,5,2))$ - $((0,7,4),(1,5,2))$ # 约束条件 - $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$ - 所有输入值均为整数。 由 ChatGPT 5 翻译