BITTUP - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Daanish Mahajan and Souradeep
Tester: Istvan Nagy
Editorialist: Taranpreet Singh

DIFFICULTY

Simple

PREREQUISITES

Basic Maths

PROBLEM

Chef has two numbers N and M. Help Chef to find number of integer N-tuples (A_1, A_2, \ldots, A_N) such that 0 \leq A_1, A_2, \ldots, A_N \leq 2^M - 1 and A_1 \& A_2 \& \ldots \& A_N = 0, where \& denotes the bitwise AND operator.

QUICK EXPLANATION

  • For each bit, we can choose a subset of given N integers, which shall have a current bit set. Only bad case is when all N integers have the current bit set. So there are 2^N-1 ways to choose a subset of positions having current bit set.
  • Subsets of positions having ith bit on is independent of values of other bits. So for each bit, we have 2^N-1 ways, leading to (2^N-1)^M

EXPLANATION

Solving for M = 1

We have to choose N integers where each integer may be 0 or 1 such that the bitwise AND of these numbers is zero. There are total 2^N ways to select integers, since we have two choices for each of the N integers.

The only bad case, where bitwise AND of numbers is non-zero, is when all values are 1. Subtracting from 2^N, we can see that there are 2^N-1 ways to choose N integers such that their bitwise AND is zero.

Intuitively, this makes sense. Let’s assume S denotes the set of positions of 1s. There are 2^N such subsets. The only subset, which has non-zero AND is when all positions are included. There’s only 1 such subset. Hence, the number of subsets of positions with zero AND is 2^N-1

Solving for M > 1

Let us try to extend our previous solution. What happens when M = 2?

We know from the definition of bitwise AND, that AND operation is applied individually on each bit. Hence, for each bit, we need to choose a subset of N positions with bitwise AND to be 0. Hence, for each bit, there are 2^N-1 valid ways to choose subsets of positions with that bit on.

Since each bit is independent of each other, then by Fundamental Rule of Counting, we can see that the number of ways would be multiplied, resulting in \displaystyle \prod_{i = 1}^M (2^N-1) = (2^N-1)^M

Implementation

Since we need to compute (2^N-1)^M \bmod MOD, we need to use binary exponentiation, as computing powers linearly will time out.

Article on Fundamental rule of counting here.
Some good resources explaining Binary Exponentiation are this, this and this

TIME COMPLEXITY

SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>
# define pb push_back 
#define pii pair<int, int>
#define mp make_pair
# define ll long long int

using namespace std;
const int maxn = 1e6 + 10, maxm = 1e6 + 10, mod = 1e9 + 7;
ll dp[maxn];
ll add(ll a, ll b){
    a += b;
    if(a >= mod)a -= mod;
    return a;
}
ll mul(ll a, ll b){
    a *= b;
    if(a >= mod)a %= mod;
    return a;
}
ll rpe(ll a, ll b){
    ll ans = 1;
    while(b != 0){
        if(b & 1)ans = mul(ans, a);
        a = mul(a, a); b >>= 1;
    }
    return ans;
}
int main()
{   
    dp[0] = 1;
    for(int i = 1; i < maxn; i++)dp[i] = dp[i - 1] * 2 % mod;
    int t; cin >> t;
    int n, m;
    while(t--){
        cin >> n >> m;
        cout << rpe((dp[n] + mod - 1) % mod, m) << endl;
    }
} 
Tester's Solution
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>

#ifdef HOME
    #include <windows.h>
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T &a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;


long long readInt(long long l, long long r, char endd) {
    long long x = 0;
    int cnt = 0;
    int fi = -1;
    bool is_neg = false;
    while (true) {
	    char g = getchar();
	    if (g == '-') {
		    assert(fi == -1);
		    is_neg = true;
		    continue;
	    }
	    if ('0' <= g && g <= '9') {
		    x *= 10;
		    x += g - '0';
		    if (cnt == 0) {
			    fi = g - '0';
		    }
		    cnt++;
		    assert(fi != 0 || cnt == 1);
		    assert(fi != 0 || is_neg == false);

		    assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
	    }
	    else if (g == endd) {
		    assert(cnt > 0);
		    if (is_neg) {
			    x = -x;
		    }
		    assert(l <= x && x <= r);
		    return x;
	    }
	    else {
		    //assert(false);
	    }
    }
}

string readString(int l, int r, char endd) {
    string ret = "";
    int cnt = 0;
    while (true) {
	    char g = getchar();
	    assert(g != -1);
	    if (g == endd) {
		    break;
	    }
	    cnt++;
	    ret += g;
    }
    assert(l <= cnt && cnt <= r);
    return ret;
}
long long readIntSp(long long l, long long r) {
    return readInt(l, r, ' ');
}
long long readIntLn(long long l, long long r) {
    return readInt(l, r, '\n');
}
string readStringLn(int l, int r) {
    return readString(l, r, '\n');
}
string readStringSp(int l, int r) {
    return readString(l, r, ' ');
}

template<typename T>
T powMod(T a, T pw, T mod)
{
    T res(1);
    while (pw)
    {
	    if (pw & 1)
	    {
		    res = (res * a) % mod;
	    }
	    pw >>= 1;
	    a = (a * a) % mod;
    }
    return res;
}

int main(int argc, char** argv) 
{
#ifdef HOME
    if(IsDebuggerPresent())
    {
	    freopen("../in.txt", "rb", stdin);
	    freopen("../out.txt", "wb", stdout);
    }
#endif
    int T = readIntLn(1, 100'000);
    const int64_t MOD = 1'000'000'007;
    forn(tc, T)
    {
	    int64_t N = readIntSp(1, 1'000'000);
	    int64_t M = readIntLn(1, 1'000'000);
	    int64_t a = powMod<int64_t>(2, N, MOD);
	    --a;//a cannot be zero, so we can subtract
	    int64_t r = powMod<int64_t>(a, M, MOD);
	    printf("%lld\n", r);
    }
    assert(getchar() == -1);
    return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class BITTUP{
    //SOLUTION BEGIN
    final long MOD = (long)1e9+7;
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni(), M = ni();
        long candidates = (pow(2, N)+MOD-1)%MOD;
        long ways = pow(candidates, M);
        pn(ways);
    }
    long pow(long a, long p){
        long o = 1;
        while(p > 0){
            if(p%2 == 1)o = o*a%MOD;
            a = a*a%MOD;
            p /= 2;
        }
        return o;
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new BITTUP().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

6 Likes

binary exponentiation (some examples i felt like sharing)
let say we want to calculate 7³¹

we have 31 = 2⁴ + 2³ +2² 2¹ + 2⁰
so
we can calculate
7 ¹⁶ ⁺ ⁸ ⁺ ⁴ ⁺² ⁺ ¹

equivalently, (7⁸)² * (7⁴)² * (7² )² * (7¹)² * (7¹)

observed something if intially, x
then the terms in multiplication are

x
(x*x)
(x*x)*(x*x)
.
.
so on   

here i choose the special case 31 where binary is (11111)₂

but let say it is 20 the binary is (10100)₂

so the 7²⁰ will be 7⁽¹⁶ ⁺ ⁴ ⁾
equivalently, (7⁸)² * 1 * (7² )² * 1 * 1

compare the case of 31 and 24 .

to calculate xⁿ
binary representation of n play a vital role
and since binary of n can be at max nearly lg₂n
so we can easily calculate xⁿ in O( lg₂n)

In editorial its nicely explained
that we want to calculate

(2ᴺ -1)ᴹ

let say mod = (10⁹ + 7)

(2ᴺ -1)ᴹ % mod is what we want finally

equivalently

{ (2ᴺ -1)*(2ᴺ -1)*.......*(2ᴺ -1) } % mod

also we know
(a*b)%p = ( (a%p)*(b%p) )%p

so { (2ᴺ -1)*(2ᴺ -1)*.......*(2ᴺ -1) } % mod
equals { [(2ᴺ -1)%mod]*[(2ᴺ -1)%mod]*.......*[(2ᴺ -1)%mod] } % mod

hence, first we need to calculate
[(2ᴺ -1)%mod]

let say A= [(2ᴺ -1)%mod]

also we know
(a-b)%p = ( (a%p)-(b%p) )%p

so (2ᴺ -1)%mod
equals [ (2ᴺ )%mod - (1%mod) ] % mod
equals [ (2ᴺ )%mod - 1 ] % mod

to the point

  • we calculate p = (2ᴺ)%mod using binary exponentiation
    finally we get A = (p-1)%mod

  • and again we calculate Aᴹ%mod using binary exponentation

so we used the above binary exponentiation technique twice to get our desired answer i.e. Aᴹ%mod

8 Likes

A more difficult problem is where the Ai are required to be distinct and in ascending order. I have no idea how to solve this modified problem for even small M, beyond brute force for up to M = 4.

2 Likes

If someone interested
Here is a similar problem.

1 Like

Practice link not working. Please check!