Even Odd Partition | CodeChef Solution

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

Even Odd Partition | CodeChef Solution

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 S0(n) = f(n) and Sk + 1 (n) = Sk(1) + Sk(2) + Sk(3) +. . .+ Sk(n) for k ≥ 0.
Given n and k, find Sk(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
    Sk (n) mod 998 244 353

Constraints

  • 1 ≤ T ≤ 3000
  • 0 ≤ k ≤ 3000
  • 1 ≤ n ≤ 1018
  • 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.

Leave a Comment

Your email address will not be published. Required fields are marked *