Codechef September long challenge 2021 | Treasure Hunt Solution

 

Codechef September long challenge 2021 | Treasure Hunt Solution

• Post published:-TechTalkBot
• Post 

Chef lives in an N×MN×M grid. He is currently participating in a treasure hunt, and has two items left to find. Chef knows that the Manhattan distance between the cells containing these two items is exactly kk. He wants to know, in how many different pairs of cells can the two items be present?

Let AkAk be the number of desired pairs when the value of Manhattan distance between the two cells containing these two items is equal to kk. Let C=∑N+M−2i=1Ai⋅31i−1C=∑i=1N+M−2Ai⋅31i−1. You have to find the value of CC.

The answer may be large, so you need to find it modulo 998244353998244353.

The Manhattan distance between two points (x,y)(x,y) and (x′,y′)(x′,y′) is defined as |x−x′|+|y−y′||x−x′|+|y−y′|.

Input Format

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• Each testcase contains of a single line of input, two integers NN and MM.

Output Format

On a new line for each test case, print CC modulo 998244353998244353

Constraints

• 1≤T≤51≤T≤5
• 1≤N,M≤1071≤N,M≤107
• The sum of NN over all tests does not exceed 107107.
• The sum of MM over all tests does not exceed 107107.

Subtasks

Subtask #1 (5 points):

• 1≤N,M≤1041≤N,M≤104
• The sum of NN over all tests does not exceed 104104.
• The sum of MM over all tests does not exceed 104104.

Subtask #2 (35 points):

• 1≤N,M≤1061≤N,M≤106
• The sum of NN over all tests does not exceed 106106.
• The sum of MM over all tests does not exceed 106106.

Subtask #3 (60 points): original constraints

Sample Input 1 

3
2 3
2 4
100 350

Sample Output 1 

2115
65668
895852507

Explanation

Test case 11:
The pairs of points with distance 11 are:

• (1,1)(1,1) and (1,2)(1,2)
• (1,1)(1,1) and (2,1)(2,1)
• (1,2)(1,2) and (1,3)(1,3)
• (1,2)(1,2) and (2,2)(2,2)
• (1,3)(1,3) and (2,3)(2,3)
• (2,1)(2,1) and (2,2)(2,2)
• (2,2)(2,2) and (2,3)(2,3)

The pairs of points with distance 22 are:

• (1,1)(1,1) and (1,3)(1,3)
• (1,1)(1,1) and (2,2)(2,2)
• (1,2)(1,2) and (2,3)(2,3)
• (1,2)(1,2) and (2,1)(2,1)
• (1,3)(1,3) and (2,2)(2,2)
• (2,1)(2,1) and (2,3)(2,3)

The pairs of points with distance 33 are:

• (1,1)(1,1) and (2,3)(2,3)
• (2,1)(2,1) and (1,3)(1,3)

Therefore, the answer is 7⋅310+6⋅311+2⋅3127⋅310+6⋅311+2⋅312 = 21152115.