[Solution] Chef And Array Construction solution codechef

Chef And Array Construction solution codechef – Given two positive integers N and M, let S denote the set of all the arrays of size N such that each element of the array lies in the range [1, M]. Since there are M^N such arrays, the size of S is M^N.

Table of Contents

[Solution] Chef And Array Construction solution codechef

Let X_i denote the bitwise AND of all elements of the i^{th} array in the set, where 1 \le i \le M^N.
Find the value \sum_{i = 1}^{M^N} X_i. Since the answer can be huge, output the answer modulo 998244353.

Input Format

  • The first line of input will contain a single integer T, denoting the number of test cases.
  • The first and only line of each test case contains two integers N and M, the size of the array, and the maximum limit of elements.

Output Format

For each test case, print the value \sum_{i = 1}^{M^N} X_i. Since the answer can be huge, output the answer modulo 998244353.

[Solution] Chef And Array Construction solution codechef

  • 1 \leq T \leq 1000
  • 1 \leq N \leq 2\cdot10^5
  • 1 \leq M \leq 10^9

Sample 1:

Input

Output

2
2 2
2 3
3
12

[Solution] Chef And Array Construction solution codechef Explanation:

Test case 1: The set S contains \{[1,1], [1,2], [2,1], [2,2]\}. The array X = [1\& 1, 1\& 2, 2\& 1, 2\& 2] = [1, 0, 0, 2]. Thus, sum of all elements of X is 1+0+0+2 = 3.

Test case 2: The set S contains \{[1,1], [1,2], [1,3], [2,1], [2,2], [2,3], [3,1], [3,2], [3,3]\}. The array X = [1\& 1, 1\& 2, 1\& 3, 2\& 1, 2\& 2, 2\& 3, 3\& 1, 3\& 2, 3\& 3] = [1, 0, 1, 0, 2, 2, 1, 2, 3]. Thus, sum of all elements of X is 12.

For Solution

“Click Here”

Leave a Comment