Even Odd Partition | CodeChef Solution

Hello coders, today we are going to solve Even Odd Partition CodeChef Solution whose Problem Code is PARTN01.

Task

Let f(n) be the number of ways to partition the array [1, 2, 3, . . . , n] into contiguous subarrays such that every pair of adjacent subarrays in the partition have sums of different parity.

• What is a contiguous subarray?
• What is a partition of an array into contiguous subarrays?
• Which partitions are counted in f(n)?

Let S₀(n) = f(n) and S_k + 1 (n) = S_k(1) + S_k(2) + S_k(3) +. . .+ S_k(n) for k ≥ 0.
Given n and k, find S_k(n) mod 998 244 353.

Input

• The first line contains a single integer T, the number of test cases.
• The first and only line of each test case contains two integers n, k.

Output

• For each test case print in a separate line, the value of
  S_k (n) mod 998 244 353

Constraints

• 1 ≤ T ≤ 3000
• 0 ≤ k ≤ 3000
• 1 ≤ n ≤ 10¹⁸
• The sum of k over all test cases does not exceed 3000.

Sample Input

12
1 0
2 0
3 0
4 0
5 0
2 1
2 2
3 3
4 4
5 5
1000000000000000000 200
1000000000000000000 2773

Sample Output

1
2
2
3
6
3
4
14
51
191
13413678
697825985

Solution – Even Odd Partition

C++

Python

Java

Disclaimer: The above Problem (Even Odd Partition) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.