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.

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. Required fields are marked *