| 题目名称 | 2179. Also Or Link |
|---|---|
| 输入输出 | or2.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 20 |
| 题目来源 |
 Zayin
于2016-03-20加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：2， 提交：3， 通过率：66.67% | ||||
 zhengtn03 |
100 | 0.005 s | 0.30 MiB | C++ |
 Zayin |
100 | 0.006 s | 0.31 MiB | C++ |
|
zhengtn03 |
95 | 0.005 s | 0.30 MiB | C++ |
| 关于 Also Or Link 的近10条评论(全部评论) |
|---|
【题目描述】
给定两个整数 N 和 K。
请你计算有多少长度为 K 的序列 A1, A2, ..., AK，(0<=Ai) 满足：
A1 Or A2 Or ...Or AK = N。
并且对于任意的 i = 1, ..., k - 1 有 Ai Or Ai + 1 = Ai + 1。
【提示】
Or 是按位或操作。
Pascal 为 or ，C 和 C++为 |。
【输入格式】
此题有多组数据。
第一行包含一个整数 T ，表示测试数据组数。
接下来有 T 行，每行包括两个整数 N 和 K ,意义如题目所述。
【输出格式】
对于每组测试数据，输出一行表示对应的答案。考虑答案可能很大，输出模 1000000009 后的结果。
【样例输入】
3
2 3
2 4
3 3
【样例输出】
3
4
9
【数据范围】
对于10%的数据，N<=100,K<=100 ；
对于30%的数据，N<=1000,K<=10000 ；
对于50%的数据，N<=10000,K<=100000 ；
对于70%的数据，N<=10000000,K<=100000000 ；
对于100%的数据，N<=100000000,K<=10000000000，T<=100 。
【来源】
By Zayin.