Even Odd Partition Codechef Solution

Even Odd Partition Codechef Solution

Let f(n)f(n) be the number of ways to partition the array [1,2,3,…,n][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)f(n)?

Let S0(n)=f(n)S0(n)=f(n) and Sk+1(n)=Sk(1)+Sk(2)+Sk(3)+⋯+Sk(n)Sk+1(n)=Sk(1)+Sk(2)+Sk(3)+⋯+Sk(n) for k≥0k≥0.
Given nn and kk, find Sk(n)mod998 244 353Sk(n)mod998 244 353.

See Also : July Long Challenge 2021 Solutions Codechef

Input

• The first line contains a single integer TT, the number of test cases.
• The first and only line of each test case contains two integers nn, kk.

Output

• For each test case print in a separate line, the value of Sk(n)mod998 244 353Sk(n)mod998 244 353.

Constraints

• 1≤T≤30001≤T≤3000
• 0≤k≤30000≤k≤3000
• 1≤n≤10181≤n≤1018
• The sum of kk over all test cases does not exceed 30003000.

Subtasks

• Subtask #1 (1 point):
  • n≤20n≤20
  • The time limit for this subtask is 1 second.
• Subtask #2 (4 points):
  • n≤1000n≤1000 (Time limit : 1 sec)
  • The time limit for this subtask is 1 second.
• Subtask #3 (10 points):
  • n≤106n≤106
  • k=0k=0 for all test cases.
  • The time limit for this subtask is 2 seconds.
• Subtask #4 (20 points):
  • The sum of kk is at most 100100.
  • The time limit for this subtask is 2 seconds.
• Subtask #5 (25 points):
  • The sum of kk is at most 30003000.
  • k≤100k≤100 and is same for all test cases.
  • The time limit for this subtask is 2 seconds.
• Subtask #6 (40 points):
  • Original constraints
  • The time limit for this subtask is 2 seconds.

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

Explanation

We first find f(n)f(n) for n=1,2,3,4,5n=1,2,3,4,5.

When n=1n=1, there is only one partition [1][1]. Since there is only one subarray, there are no adjacent subarrays in this partition and hence should be counted in f(1)f(1), therefore f(1)=1f(1)=1.

When n=2n=2, there are 22 partitions possible, [1,2][1,2] and [1],[2][1],[2]. The first partition has no adjacent subarrays and so is counted in f(2)f(2).
The second partition has sums 1,21,2 which are alternating in parity and so is also counted in f(2)f(2), therefore f(2)=2f(2)=2.

When n=3n=3, there are 44 partitions possible. The partitions are shown below.

There are in total 22 partitions whose subarrays sums are alternating in parity, therefore f(3)=2f(3)=2

When n=4n=4, there are 88 partitions. The partitions are shown below.

There are in total 22 partitions whose subarrays sums are alternating in parity, therefore f(3)=2f(3)=2

When n=5n=5, there are in total 1616 partitions. The partitions are shown below.

There are in total 66 partitions whose subarray sums are alternating in parity, therefore f(5)=6f(5)=6

S0(n)=f(n)S0(n)=f(n) and is found as described above.

To find S1(n),S2(n),…S1(n),S2(n),…, the given formula Sk+1(n)=Sk(1)+Sk(2)+⋯+Sk(n)Sk+1(n)=Sk(1)+Sk(2)+⋯+Sk(n) is used.
For example S1(n)=S0(1)+S0(2)+⋯+S0(n)S1(n)=S0(1)+S0(2)+⋯+S0(n).

The values for Sk(n)Sk(n) for k≤5k≤5 and n≤5n≤5 are tabulated below.

Solution

#include<bits/stdc++.h>
using namespace std;
int main() {
	long long int a[1000005],s[3005][1005],b1[3005];
	long long int c,n,g,t;
	a[1]=1;
	long long b=998244353;
	long long int oe=0,ee=0,oo=0,ne=0,no=1,eo=0;
	long long int oe1,ee1,oo1,ne1,no1,eo1,num;
	for(long long int i=2;i<1000004;i++)
	{
	    c=0;
	    if(i%2==0)
	    {
	        c=(oe%b)+(ne%b)+(no%b)+(no%b)+(eo%b)+(eo%b);
	        oe1=(no*1)+(eo*1);
	        ee1=oe*1+ne*1;
	        oe=(oe+oe1)%b;
	        ee=(ee+ee1)%b;
	    }
	    else
	    {
	        c=(oe%b)+(ee%b)+(oo%b)+(ne%b)+(ne%b)+(no%b);
	        oe1=oo%b;
	        oo1=(no+eo+oe)%b;
	        ee1=eo%b;
	        eo1=(oe+ne+ee)%b;
	        no1=ne%b;
	        ne1=no%b;
	        oe=oe1;
	        oo=oo1;
	        ee=ee1;
	        eo=eo1;
	        no=no1;
	        ne=ne1;
	    }
	    a[i]=c%b;
	}
	for(int i=1;i<=1003;i++)
	{
	    s[0][i]=a[i];
	}
	for(int i=0;i<3005;i++)
	{
	    s[i][0]=0;
	    s[i][1]=1;
	}
	for(long long int i=1;i<3002;i++)
	{
	    for(long long int j=2;j<=1003;j++)
	    {
	        s[i][j]=(s[i][j-1]+s[i-1][j])%b;
	    }
	}
	cin>>t;
	for(int t1=0;t1<t;t1++)
	{
	    cin>>n>>g;
	    if(g==0)
	    {
	        b1[t1]=a[n];
	    }
	    else
	    {
	        b1[t1]=s[g][n];
	    }
	}
	for(int t1=0;t1<t;t1++)
	{
	    cout<<b1[t1]<<endl;
	}
	return 0;
}

July Long Challenge 2021 Solutions

• Maximum Production
• Relativity
• XxOoRr
• Optimal Denomination
• K Path Query
• Chef vs Bharat
• Chef and Pairs
• Even Odd Partition
• Dakimakura Distribition
• Madoka and Ladder Decomposition

Weekly Contest 247

• Maximum Product Difference Between Two Pairs
• Cyclically Rotating a Grid
• Number of Wonderful Substrings
• Count Ways to Build Rooms in an Ant Colony

Biweekly Contest 55

• Remove One Element to Make the Array Strictly Increasing
• Remove All Occurrences of a Substring
• Maximum Alternating Subsequence Sum
• Design Movie Rental System