一.题意
巴达维宝宝的第一句话是“0和大”，所以他决定解决下面的问题。给定两个整数n和k，计算长度为n的数组的数目，以便：
它的所有元素都是0到2^k?1(包含2^k-1)；
其所有元素的位“与”为0；
它的元素之和尽可能大。
因为答案可能非常大，所以在除以109+7时打印其余数。
二.输入输出
?
输入
第一行包含整数t（1≤T≤10） -需要解决的测试用例数。
每个测试用例由一条包含两个整数n和k组成1≤N≤10^5, 1≤K≤20).
输出
对于每个测试用例，打印满足条件的数组数。因为答案可能非常大，所以在模109+7时输出其余数。
三.思路
1.数组中元素不大于2 k ? 1 2^k-12?
k
??1，即每个元素在二进制中最大为k位；
2.要满足所有元素按位&运算为0，即数组中每个元素化为二进制对齐后，每个位数至少有一个0。说的可能有点抽象，举个例子：
在n=3，k=5时，在不考虑【元素和尽量大】这一条件的时候，可能满足按位&=0的数组有：
a[0]=0 1 1 0 1( 2 ) _{(2)}?
(2)
??? ?
?
a[1]=1 0 0 1 0( 2 ) _{(2)}?
(2)
??? ?
?
a[2]=0 1 1 0 1( 2 ) _{(2)}?
(2)
??? ?
?
即化为二进制对齐后，每列至少存在一个0
3.要满足数组元素和尽量大，则要满足每列的1尽可能多。则只需要每列存在一个0时满足题意。此时数组元素和为( 2 k ? 1 ) ? ( n ? 1 ) (2^k-1)*(n-1)(2?
k
??1)?(n?1)。
如例子：
在n=3，k=5时：
a[0]=1 1 1 0 1( 2 ) _{(2)}?
(2)
??? ?
?
a[1]=1 0 0 1 0( 2 ) _{(2)}?
(2)
??? ?
?
a[2]=0 1 1 1 1( 2 ) _{(2)}?
(2)
??? ?
?
4.分析完题意所给的条件后，我们知道，0在每一列中有n种放置情况，共有k列。即答案为n k n^kn?
k
?。由于n的范围到了1e5，可用快速幂水一下。
///思路借鉴 自己表达的没那么好
四.上板子
#include<iostream>
using namespace std;
int mood = 1e9 + 7;
typedef long long ll;
int main() {
int T;
cin >> T;
while (T--)
{
ll a, b;
cin >> a >> b;
ll ans = 1;
while (b--) {
ans *= a;
ans = ans % (mood);
}
cout << ans << endl;
}
return 0;
}
?
|