[Solved] Magical Orb Newton’s Triwizard Contest with Java

An array A of size N is called magical if:

1. Each element of the array is a positive integer not exceeding M, that is, 1 ≤ Ai ≤ M for each i.

2. For each i such that 1 ≤ i ≤ N, define f(i) = A1 | A2 | … Ai, where x | y denotes the bitwise OR of x and y.

Then, f(1) = f(2) = … f(N) must hold.

Your task is to calculate the number of magical arrays of size N, modulo 998244353.

Input

The input consists of two space-separated integers N and M.

Constraints:

1 ≤ N ≤ 105

1 ≤ M ≤ 105

Output

Print a single integer – the number of magical arrays modulo 998244353.

Example

Sample Input 1:

2 3

Sample Output 1:

5

Sample Explanation:

The magical arrays are: [1, 1], [2, 2], [3, 3], [3, 1], [3, 2].

Sample Input 2:

1 50

Sample Output 2:

50

Sample Input 3:

707 707

Sample Output 3:

687062898

Solution

Steps to solve this problem:

Step 1: First, we will count the number of set bits in the number i. We will use the function count_set_bits() for this.

Step 2: Now, we will calculate the value of base. The value of base is 2^x-1, where x is the number of set bits in the number i.

Step 3: Now, we will calculate the value of val. The value of val is base^(n-1). We will use the function powerOfn() for this.

Step 4: Now, we will add the value of val to the variable ans.

Step 5: Finally, we will print the value of ans.

import java.io.*; // for handling input/output
import java.util.*; // contains Collections framework

// don't change the name of this class
// you can add inner classes if needed
class Main {
    public static void main (String[] args) {
        // Your code here
               Scanner sc = new Scanner(System.in);
       int n = sc.nextInt();
       int m = sc.nextInt();
       long ans =0;
       int mod = 998244353;
       for(int i=1;i<=m;i++){
           long val =0;
           int x = count_set_bits(i);
           int base = (int)Math.pow(2,x)-1;
           int pow = n-1;
           val = powerOfn(base,pow,mod);
           ans = (ans+val)%mod;
       }
        System.out.println(ans);
    }

    static int count_set_bits(int n){
        int count=0;
        while(n>0){
            n &= (n-1);
            count++;
        }
        return count;
    }
    static long powerOfn(long a,long n,int mod){
        if(n==0){
            return 1;
        }
        if(n%2==0){
            return powerOfn((a*a)%mod,n/2,mod) %mod;
        }
        return (a%mod)*powerOfn((a*a)%mod,(n-1)/2, mod) %mod; // for odd n
    }
}

Happy Learning – If you require any further information, feel free to contact me.