Array Partition solution codechef – You are given an array A of N integers, and an integer X. For each K in the range [1,N], determine the number of ways to partition the array into exactly K non-empty subarrays such that the maxima of each of the subarrays are at least X.

  • Array Partition solution codechef
    For Solution

    Click Here!

You are given an array AA of NN integers, and an integer XX. For each KK in the range [1,N][1,N], determine the number of ways to partition the array into exactly KK non-empty subarrays such that the maxima of each of the subarrays are at least XX.

The number of ways can be large, so output it modulo 998244353998244353.

Note: The input and output are large, so use fast input-output methods.

Input Format

  • The first line of input contains a single integer TT, denoting the number of test cases. The description of TT test cases follows.
  • Each test case contains two lines of input.
  • The first line of each test case consists of two space-separated integers NN and XX.
  • The second line consists of NN space-separated integers denoting the elements of the array AA.

Output Format

For each test case, output a single line containing NN space-separated integers, the ii-th of which denotes the number of ways to partition the array into exactly ii non-empty subarrays such that the maxima of each of the ii subarrays are at least XX. Print the answer modulo 998244353998244353.

Constraints

  • 1T71041≤T≤7⋅104
  • 1N1061≤N≤106
  • 1X1091≤X≤109
  • 1Ai1091≤Ai≤109
  • The sum of NN across all test cases does not exceed 106106

Subtasks

Subtask #1 (20 points):

  • 1T2001≤T≤200
  • 1N1031≤N≤103
  • The sum of NN across all test cases does not exceed 21032⋅103
  • Time Limit = 11 second

Subtask #2 (80 points):

  • Original constraints
  • Time Limit = 1.751.75 seconds

Sample Input 1 

3
5 3
4 1 7 1 6
4 2
2 2 2 1
3 4
5 6 7

Sample Output 1 

1 4 4 0 0 
1 2 1 0 
1 2 1

Explanation

In the below explanation, [L,R][L,R] denotes the subarray consisting of elements AL,AL+1,,ARAL,AL+1,…,AR.

Test case 11:

  • The number of partitions having exactly 11 subarray is 11, which is the array itself.
  • The number of partitions having exactly 22 subarrays is 44, which are [1,1][1,1]+[2,5][2,5][1,2][1,2]+[3,5][3,5][1,3][1,3]+[4,5][4,5][1,4][1,4]+[5,5][5,5].
  • The number of partitions having exactly 33 subarrays is 44, which are [1,1][1,1]+[2,3][2,3]+[4,5][4,5][1,1][1,1]+[2,4][2,4]+[5,5][5,5][1,2][1,2]+[3,3][3,3]+[4,5][4,5][1,2][1,2]+[3,4][3,4]+[5,5][5,5].
  • The number of partitions having 44 or 55 subarrays is 00.

Test case 22:

  • The number of partitions having exactly 11 subarray is 11, which is the array itself.
  • The number of partitions having exactly 22 subarrays is 22, which are [1,1][1,1]+[2,4][2,4][1,2][1,2]+[3,4][3,4].
  • The number of partitions having exactly 33 subarrays is 11, which is [1,1][1,1]+[2,2][2,2]+[3,4][3,4].
  • The number of partitions having exactly 44 subarrays is 00.

Test Case 33:

  • The number of partitions having exactly 11 subarray is 11, which is the array itself.
  • The number of partitions having exactly 22 subarrays is 22, which are [1,1][1,1]+[2,3][2,3][1,2][1,2]+[3,3][3,3].
  • The number of partitions having exactly 33 subarrays is 11, which is [1,1][1,1]+[2,2][2,2]+[3,3][3,3].
  • For Solution

    Click Here!

Leave a Comment

Your email address will not be published.