Chef And Division CodeChef Solution | CodeChef Problem Solution 2022

Chef And Division CodeChef Solution | CodeChef Problem Solution 2022 

You are given an array A$A$ of size N$N$.

A partitioning of the array A$A$ is the splitting of A$A$ into one or more non-empty contiguous subarrays such that each element of A$A$ belongs to exactly one of these subarrays.

Find the number of ways to partition A$A$ such that the parity of the sum of elements within the subarrays is alternating. In other words, if Si$S_i$ denotes the sum of the elements in the i$i$-th subarray, then either

• S1$S_1$ is odd, S2$S_2$ is even, S3$S_3$ is odd and so on.
• or S1$S_1$ is even, S2$S_2$ is odd, S3$S_3$ is even and so on.

For example if A=[1,2,3,3,5]$A=[1,2,3,3,5]$. One way to partition A$A$ is [1,2][3,3][5]$[1,2][3,3][5]$. Another way to partition A$A$ is [1][2][3][3,5]$[1][2][3][3,5]$. Note that there exists more ways to partition this array.

Solution Click Below:- 

Since the answer may be large, output it modulo 998244353$998244353$.

Input Format

• The first line contains a single integer T$T$ - the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer N$N$ - the size of the array A$A$.
• The second line of each test case contains N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$ denoting the array A$A$.

Output Format

For each test case, output the answer modulo 998244353$998244353$.

Constraints

• 1≤T≤10000$1\le T\le 10000$
• 1≤N≤2⋅105$1\le N\le 2\cdot {10}^5$
• 0≤Ai≤109$0\le A_i\le {10}^9$
• Sum of N$N$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$

Sample Input 1 

3
3
1 2 3
4
4 4 4 4
5
1 2 3 3 5

Sample Output 1 

2
1
5

Explanation

Test case 1: The array can be partitioned as follows

• [1][2][3]$[1][2][3]$
• [1,2,3]$[1,2,3]$

Test case 2: The array can be partitioned as follows

Flip to Invert Solution CodeChef | CodeChef Problem Solution 2022

Akash and Equal Mean Solution | CodeChef Problem Solution 

Flip to Invert Solution CodeChef 

Antipodal Points Solution

Join Now for Solution:- 

Best Coupon Solution | CodeChef Problem Solution 2022

Chef And Division CodeChef Solution | CodeChef Problem Solution 2022