B. AND 0, Sum Big
time limit per test
2 seconds
memory limit per test
256 megabytes
题目描述
Baby Badawy’s first words were “AND 0 SUM BIG”, so he decided to solve the following problem. Given two integers n and k, count the number of arrays of length n
such that:
- all its elements are integers between 0 and
(inclusive) - the bitwise AND of all its elements is 0;
- the sum of its elements is as large as possible.
Since the answer can be very large, print its remainder when divided by .
Input
The first line contains an integer t(1≤t≤10) — the number of test cases you need to solve.
Each test case consists of a line containing two integers n and k (1≤n≤, 1≤k≤20).
Output
For each test case, print the number of arrays satisfying the conditions. Since the answer can be very large, print its remainder when divided by .
Example
Input
2
2 2
100000 20
Output
4
226732710
Note
In the first example, the 4arrays are:
- [3,0],
- [0,3],
- [1,2],
- [2,1].
题意
输入n,k。
有长度为n的数组满足下面三个条件：
- 数组元素要小于等于，大于等于0
- 数组内所有元素的类与（and或&）要为0
- 数组元素总和要最大
注意，元素可以重复。
问这样的数组可以找到多少个？
思路
1、数组元素要小于等于，大于等于0，表明：数组内的每个元素都可以由长度为k的二进制数表示。
2、数组内所有元素的类与（and或&）要为0，说明：由1，我们可以把一维数组看出二维数组（行数为n，列数为k），则由要求2，那么每一列需要且仅需要一个0
3、数组元素总和要最大，所以一列只能有一个零，不然的话，就不会总和最大了。
由1，2，3，=====》要求的数就是n^k。
注意
可能n^k数太大，所以得用快速幂。
AC代码
#include<iostream>
#include<algorithm>
#include<math.h>
typedef long long ll;
using namespace std;
const int N = 1e9+7;
ll n,t,k;
int main(){
cin>>t;
while(t--){
cin>>n>>k;
ll ans = 1;
while(k){
if(k&1){
ans = (ans*n)%N;
}
n = (n*n)%N;
k>>=1;
}
cout<<ans<<endl;
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/103315.html
