Hello coders, today we are going to solve Bitwise Tuples CodeChef Solution in C++, Java and Python.
Task
Chef has two numbers N and M. Help Chef to find number of integer N-tuples (A1,A2,…,AN) such that 0≤A1,A2,…,AN≤2M−1 and A1&A2&…&AN=0, where & denotes the bitwise AND operator.
Since the number of tuples can be large, output it modulo 109+7.
Input
- The first line contains a single integer T denoting the number of test cases. The description of T test cases follows.
- The first and only line of each test case contains two integers N and M.
Output
For each test case, output in a single line the answer to the problem modulo 109+7.
Constraints
- 1≤T≤105
- 1≤N,M≤106
Subtasks
Subtask #1 (100 points): original constraints
Sample Input
4
1 2
2 2
4 2
8 4
Sample Output
1
9
225
228250597
Explanation
Test Case 1: The only possible tuple is (0).
Test Case 2: The tuples are (0,0), (0,1), (0,2), (0,3), (1,0), (2,0), (3,0), (1,2), (2,1).
Solution – Bitwise Tuples CodeChef Solution
#include <bits/stdc++.h> #define all(x) x.begin(),x.end() using ll = long long int; using namespace std; ll getPower(ll a, ll b){ static ll mod = 1000000007; if(b==0)return 1; if(b==1)return a; if(b%2==0){ ll ans = getPower(a,b/2); return (ans * ans) % mod; } else { ll ans = getPower(a,(b-1)/2); return ((a*ans)%mod*ans)%mod; } } int main() { // your code goes here int t; cin >>t ; while(t--){ ll a,b,temp; cin >> a >> b; temp = getPower(2,a)-1; cout << getPower(temp,b) << endl; } return 0; }
Disclaimer: The above Problem (Bitwise Tuples) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.
java ka solution nahi hai kya bhaiya?