AT_k2pc001_h2 虫歯(Cavity)

[problemUrl]: https://atcoder.jp/contests/k2pc-hard/tasks/k2pc001_h2 **※截至 20:22，集合评测似乎未能正常运行。修正后将进行重新评测。（每个测试用例显示的结果应该是正确的）** **※20:35 已修正集合评测数据并进行了重新评测。原本看似正确的提交也有可能被判为错误。请注意确认。给您带来不便，敬请谅解。** kyuridenamida 因为吃了太多零食，导致一颗牙齿蛀坏了。 由于这颗牙齿非常疼痛，他去看了牙医，牙医帮他治疗了牙齿神经中的 $N$ 个部位。 kyuridenamida 的牙齿神经如图 $1$ 所示，构成了一棵深度为 $K$ 的完全二叉树。 （关于二叉树，请参考 [Wikipedia 页面](http://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%9C%A8) 等。）  图 $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 翻译