06659. USACO·数数奶牛 · 林老师的题库

题目描述

如同平常一样，Farmer John 的奶牛们分散在他的最大的草地上。草地可以看作是一个由正方形方格组成的巨大的二维方阵（想象一个巨大的棋盘）。

奶牛分布在草地上的方式相当迷人。对于每一个满足 $x \geq 0$ 以及 $y \geq 0$ 的方格 $(x, y)$ ，当对于所有整数 $k \geq 0$ ， $⌊ \frac{x}{3 ^{k}} ⌋$ 和 $⌊ \frac{y}{3 ^{k}} ⌋$ 除以三的余数的奇偶性均相同时，有一头奶牛位于 $(x, y)$ 。换言之，两个余数均为奇数（均等于 $1$ ），或均为偶数（均等于 $0$ 或 $2$ ）。例如，满足 $0 \leq x, y < 9$ 的方格中，包含奶牛的方格在下图中用 1 表示。

012345678

0 101000101

1 010000010

2 101000101

3 000101000

y 4 000010000

5 000101000

6 101000101

7 010000010

8 101000101

FJ 对他的草地上的某个特定区域内的奶牛数量感兴趣。他进行了 $Q$ 个询问，每个询问由三个整数 $x_{i}, y_{i}, d_{i}$ 组成。对每个询问，FJ 想要知道有多少奶牛位于 $(x_{i}, y_{i})$ 至 $(x_{i} + d_{i}, y_{i} + d_{i})$ 的对角线上的方格内（包括两端）。

输入格式

输入的第一行包含 $Q$ （ $1 \leq Q \leq 1 0^{4}$ ），为询问的数量。

以下 $Q$ 行每行包含三个整数 $d_{i}$ ， $x_{i}$ 和 $y_{i}$ （ $0 \leq x_{i}, y_{i}, d_{i} \leq 1 0^{18}$ ）。

输出格式

输出 $Q$ 行，每个询问输出一行。

样例

输入

8
10 0 0
10 0 1
9 0 2
8 0 2
0 1 7
1 1 7
2 1 7
1000000000000000000 1000000000000000000 1000000000000000000

输出

11
0
4
3
1
2
2
1000000000000000001

提示说明

【样例解释】

测试点 3-6 满足对于每一个询问有 $x + d = 3^{30} - 1$ 以及 $y = 0$ 。
测试点 7-12 没有额外限制。

【数据规模与约定】

测试点 2 满足对于每一个询问有 $d_{i} \leq 100$ 。
测试点 3-6 满足对于每一个询问有 $x + d = 3^{30} - 1$ 以及 $y = 0$ 。
测试点 7-12 没有额外限制。

供题：Benjamin Qi

06659. USACO·数数奶牛 未做

题目描述

输入格式

输出格式

样例

提示说明

06659. USACO·数数奶牛未做