AT_k2pc001_h2.虫歯(Cavity)

※截至 20:22，集合评测似乎未能正常运行。修正后将进行重新评测。（每个测试用例显示的结果应该是正确的）

※20:35 已修正集合评测数据并进行了重新评测。原本看似正确的提交也有可能被判为错误。请注意确认。给您带来不便，敬请谅解。
kyuridenamida 因为吃了太多零食，导致一颗牙齿蛀坏了。
由于这颗牙齿非常疼痛，他去看了牙医，牙医帮他治疗了牙齿神经中的 $N$ 个部位。

kyuridenamida 的牙齿神经如图 $1$ 所示，构成了一棵深度为 $K$ 的完全二叉树。
（关于二叉树，请参考 Wikipedia 页面 等。）

图 $1$

在表示他神经的二叉树中，深度为 $i$，从左往右第 $j$ 个神经记作 $(i, j)$（见图 $2$）。
此时，能够沿着祖先节点一直追溯到根节点 $(0, 1)$ 的神经，被称为蛀牙神经。
但是，如果某个蛀牙神经的祖先已经被治疗，则该神经无法到达根节点 $(0, 1)$。
另外，如果 $(0, 1)$ 本身未被治疗，则认为 $(0, 1)$ 能够到达自身。

图 $2$

能够到达根节点的蛀牙神经的总数被称为牙痛值。
你的任务是，根据给出的 kyuridenamida 的蛀牙信息，计算并输出他的牙痛值。

请输出能够传递疼痛的神经的数量，输出一行。
（注意，答案可能超出 32 位整数范围。）

• $1 \leq K \leq 50$ 牙齿神经的深度
• $0 \leq N \leq 10^5$ 已治疗神经的数量
• $0 \leq p_i \leq K$ 已治疗神经 $i$ 的深度
• $1 \leq q_i \leq 2^{p_i}$ 已治疗神经 $i$ 在深度 $p_i$ 时的位置
• 若 $p_i = p_j$，则保证 $q_i \neq q_j$

对于 $40\%$ 的测试点，$N \leq 1000$。

1
1
1 1

2

9
0

1023

3
2
1 2
3 7

8

对应输入输出样例 3 的图如下所示。
其中，图中的蓝色圆圈表示已治疗的神经，红色叉号表示能够到达根节点的蛀牙神经。

第一行包含一个整数 $K$，表示牙齿神经的深度。
第二行包含一个整数 $N$，表示已治疗神经的数量。
接下来的 $N$ 行，每行包含两个整数 $p_i$ 和 $q_i$，表示第 $i$ 个已治疗神经的位置。

输出一行，表示能够传递疼痛的神经的数量。

无。

由 ChatGPT 4.1 翻译