Codeforces Round #716 (Div. 2) B&C

B - AND 0, Sum Big

题目介绍:

• 给你 t 组数据
• 每组数据n和k
• 规定:
• 每个数组都有n个元素
• 数组每个元素在 0~2^k - 1 之间
• 所有的元素求&为0
• 元素的和要尽可能大
• 输出 可能的组数

思路分析:

数组元素二进制范围: 因为每个元素都在 2^k - 1的范围内 所以对于a[i] 的二进制最多有k位

又因为对于所有元素求& 要为0 所以二进制位中,每一列至少有一个0

又因为和要尽可能大 所以每一列只需要有一个0就行了

结论: 对于每一列 0有n总摆法 总共有k列 所以总数 n^k

所以code如下

#include 
using namespace std;
typedef long long ll;
const ll mod  = 1e9+7;
int n,k;
int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        cin >> n >> k;
        ll res = 1;
        for(int i = 1 ; i