77. 位与数对个数

单点时限: 2.5 sec

内存限制: 256 MB

给定三个整数 $a,b,k$,计算满足 $x$ ($0 \le x < a$) 和 $y$ $(0 \le y < b)$ 的位与结果小于 $k$(即 $0 \le x \& y < k$)的有序数对 $(x,y)$ 的个数。

输入格式

第一行数据组数 $T$。

接下来 $T$ 行,每行三个正整数 $a,b,k$。

  • 数据点 1: 占 $30\%$, $1 \le T \le 100$, $a,b,k \le 100$;
  • 数据点 2: 占 $40\%$, $1 \le T \le 10^5$, $a,b,k \le 100$;
  • 数据点 3: 占 $30\%$, $1 \le T \le 10^5$, $a,b,k \le 10^9$.

输出格式

对于每组数据输出数对个数。

样例

Input
3
3 4 2
4 5 2
103 143 88
Output
10
16
14377

提示

$a=3,b=4,k=2$ 时,满足条件的数对有 $(0,0)$, $(0,1)$, $(0,2)$, $(0,3)$, $(1,0)$, $(1,1)$, $(1,2)$, $(1,3)$, $(2,0)$, $(2,1)$。总计是 $10$ 对。注意:$(0,1)$ 和 $(1,0)$ 是两对不同的数对。$(2,2)$ 不满足条件,因为 $2 \& 2=2$ 不满足位与结果小于 $k=2$ 的条件。

70 人解决,410 人已尝试。

100 份提交通过,共有 1386 份提交。

6.5 EMB 奖励。

创建: 6 年,9 月前.

修改: 6 年,1 月前.

最后提交: 4 月,2 周前.

来源: 2018 实训第一次机考

题目标签
DP