首页 > 其他分享 >Codeforces Round #716 (Div. 2), B. AND 0, Sum Big, 快速幂结论题

Codeforces Round #716 (Div. 2), B. AND 0, Sum Big, 快速幂结论题

时间:2023-02-08 16:07:57浏览次数:45  
标签:20 int 716 Sum Codeforces its return LL mod


problem

B. AND 0, Sum Big
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
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 2k−1 (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 109+7.

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≤105, 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 109+7.

Example
inputCopy
2
2 2
100000 20
outputCopy
4
226732710
Note
In the first example, the 4 arrays are:

[3,0],
[0,3],
[1,2],
[2,1].

B. AND 0,总和
每次测试的时限2秒
每个测试的内存限制256 MB
输入标准输入
输出标准输出
Baby Badawy的第一个单词是“ AND 0 SUM BIG”,因此他决定解决以下问题。给定两个整数n和k,计算长度为n的数组的数量,使得:

它的所有元素都是0到2k-1(含)之间的整数;
其所有元素的按位与为0;
其元素的总和应尽可能大。
由于答案可能非常大,因此请打印除以109 + 7所得的余数。

输入
第一行包含一个整数t(1≤t≤10)-您需要解决的测试用例数。

每个测试用例由包含两个整数n和k(1≤n≤105,1≤k≤20)的一行组成。

输出
对于每个测试用例,打印满足条件的数组数。由于答案可能非常大,因此请打印除以109 + 7所得的余数。

例子
inputCopy
2
2 2
100000 20
outputCopy
4
226732710
笔记
在第一个示例中,这四个数组是:

[3,0],
[0,3],
[1,2],
[2,1]。

solution

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5+10;
const int mod = 1e9+7;

LL mpow(LL a, LL x) {
if(x==0)return 1;
LL t = mpow(a, x>>1);
if(x%2==0)return t*t%mod;
return t*t%mod*a%mod;
}

int main(){
ios::sync_with_stdio(false);
//init();
int T; cin>>T;
while(T--){
int n, k; cin>>n>>k;
cout<<mpow(n,k)<<"\n";

}
return 0;
}


标签:20,int,716,Sum,Codeforces,its,return,LL,mod
From: https://blog.51cto.com/gwj1314/6044559

相关文章