Contents
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.
Partition | Sum of subarrays | Are the sum of subarrays alternating in parity ? |
---|---|---|
[1, 2, 3] | {6} | Yes |
[1], [2, 3] | {1, 5} | No |
[1, 2], [3] | {3, 3} | No |
[1], [2], [3] | {1, 2, 3} | Yes |
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.
Partition | Sum of subarrays | Are the sum of subarrays alternating in parity ? |
---|---|---|
[1, 2, 3, 4] | {10} | Yes |
[1], [2, 3, 4] | {1, 9} | No |
[1, 2], [3, 4] | {3, 7} | No |
[1], [2], [3, 4] | {1, 2, 7} | Yes |
[1, 2, 3], [4] | {6, 4} | No |
[1], [2, 3], [4] | {1, 5, 4} | No |
[1, 2], [3], [4] | {3, 3, 4} | No |
[1], [2], [3], [4] | {1, 2, 3, 4} | Yes |
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.
Partition | Sum of subarrays | Are the sum of subarrays alternating in parity ? |
---|---|---|
[1, 2, 3, 4, 5] | {15} | Yes |
[1], [2, 3, 4, 5] | {1, 14} | Yes |
[1, 2], [3, 4, 5] | {3, 12} | Yes |
[1], [2], [3, 4, 5] | {1, 2, 12} | No |
[1, 2, 3], [4, 5] | {6, 9} | Yes |
[1], [2, 3], [4, 5] | {1, 5, 9} | No |
[1, 2], [3], [4, 5] | {3, 3, 9} | No |
[1], [2], [3], [4, 5] | {1, 2, 3, 9} | No |
[1, 2, 3, 4], [5] | {10, 5} | Yes |
[1], [2, 3, 4], [5] | {1, 9, 5} | No |
[1, 2], [3, 4], [5] | {3, 7, 5} | No |
[1], [2], [3, 4],[5] | {1, 2, 7, 5} | No |
[1, 2, 3], [4], [5] | {6, 4, 5} | No |
[1], [2, 3], [4], [5] | {1, 5, 4, 5} | No |
[1, 2], [3], [4], [5] | {3, 3, 4, 5} | No |
[1], [2], [3], [4], [5] | {1, 2, 3, 4, 5} | Yes |
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.
n | S0(n) | S1(n) | S2(n) | S3(n) | S4(n) | S5(n) |
---|---|---|---|---|---|---|
1 | 1 | 1 | 1 | 1 | 1 | 1 |
2 | 2 | 3 | 4 | 5 | 6 | 7 |
3 | 2 | 5 | 9 | 14 | 20 | 27 |
4 | 3 | 8 | 17 | 31 | 51 | 78 |
5 | 6 | 14 | 31 | 62 | 113 | 191 |
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