Travel Plan
Contest: Codeforces Round 896 (Div. 1)
Difficulty rating: 2400
Tags: combinatorics, dp, implementation, math, trees

During the summer vacation after Zhongkao examination, Tom and Daniel are planning to go traveling.

There are $$$n$$$ cities in their country, numbered from $$$1$$$ to $$$n$$$. And the traffic system in the country is very special. For each city $$$i$$$ ($$$1 \le i \le n$$$), there is

- a road between city $$$i$$$ and $$$2i$$$, if $$$2i\le n$$$;
- a road between city $$$i$$$ and $$$2i+1$$$, if $$$2i+1\le n$$$.

Making a travel plan, Daniel chooses some integer value between $$$1$$$ and $$$m$$$ for each city, for the $$$i$$$-th city we denote it by $$$a_i$$$.

Let $$$s_{i,j}$$$ be the maximum value of cities in the simple$$$^\dagger$$$ path between cities $$$i$$$ and $$$j$$$. The score of the travel plan is $$$\sum_{i=1}^n\sum_{j=i}^n s_{i,j}$$$.

Tom wants to know the sum of scores of all possible travel plans. Daniel asks you to help him find it. You just need to tell him the answer modulo $$$998\,244\,353$$$.

$$$^\dagger$$$ A simple path between cities $$$x$$$ and $$$y$$$ is a path between them that passes through each city at most once.

Input format:
The first line of input contains a single integer $$$t$$$ ($$$1\le t\le 200$$$) — the number of test cases. The description of test cases follows.

The only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1\leq n\leq 10^{18}$$$, $$$1\leq m\leq 10^5$$$) — the number of the cities and the maximum value of a city.

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case output one integer — the sum of scores of all possible travel plans, modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test case, there is only one possible travel plan:

Path $$$1\rightarrow 1$$$: $$$s_{1,1}=a_1=1$$$.

Path $$$1\rightarrow 2$$$: $$$s_{1,2}=\max(1,1)=1$$$.

Path $$$1\rightarrow 3$$$: $$$s_{1,3}=\max(1,1)=1$$$.

Path $$$2\rightarrow 2$$$: $$$s_{2,2}=a_2=1$$$.

Path $$$2\rightarrow 1\rightarrow 3$$$: $$$s_{2,3}=\max(1,1,1)=1$$$.

Path $$$3\rightarrow 3$$$: $$$s_{3,3}=a_3=1$$$.

The score is $$$1+1+1+1+1+1=6$$$.

In the second test case, there are four possible travel plans:

Score of plan $$$1$$$: $$$1+1+1=3$$$.

Score of plan $$$2$$$: $$$1+2+2=5$$$.

Score of plan $$$3$$$: $$$2+2+1=5$$$.

Score of plan $$$4$$$: $$$2+2+2=6$$$.

Therefore, the sum of score is $$$3+5+5+6=19$$$.

Example input:
5
3 1
2 2
10 9
43 20
154 147

Example output:
6
19
583217643
68816635
714002110

Editorial:
For any path of length $$$t$$$, the number of assignments in which the maximum value of cities is no bigger than $$$k$$$ is $$$k^t$$$. As a result, the number of assignments in which the maximum value of cities is exactly $$$k$$$ is $$$k^t-(k-1)^t$$$, while the sum of the maximum value of cities in all assignments is $$$\sum_{k=1}^m(k^t-(k-1)^t)k$$$. We can solve this in $$$\mathcal O(m\log n)$$$.
Then, we need to calculate the number of paths of length $$$t$$$ for each $$$t$$$.
Claim. There are $$$\mathcal O(\log n)$$$ different subtrees in this tree.
Proof. It's easy to see that this tree can be seen as a full binary tree with one row of extra leaves. Let the number of leaves in each subtree be $$$lf_i$$$. If $$$lf_i=2^p$$$, the subtree of $$$i$$$ is a full binary tree with depth $$$p$$$. Also, for each subtree satisfying $$$lf_i\neq 2^p$$$, either $$$lf_{2i}=2^{p'}$$$ or $$$lf_{2i+1}=2^{p'}$$$, which means that for each depth, there is at most one subtree satisfying $$$lf_i\neq2^p$$$. As the depth of the whole tree is $$$\mathcal O(\log n)$$$, the total number of different subtrees is also $$$\mathcal O(\log n)$$$.
Then, let $$$dp_{i,j}$$$ stand for the number of paths length $$$j$$$ in a subtree with $$$i$$$ vertices, and $$$f_{i,j}$$$ stand for the number of paths with one end being $$$i$$$ and length $$$j$$$ in a subtree with $$$i$$$ vertices. We can simply do a memorization search to solve this part in $$$\mathcal O(\log^3 n)$$$.
To optimize the first part, we can transform the formula to $$$m^t\times m-\sum_{k=1}^{m-1}k^t$$$. For the second part, we can use interpolation, dp, or polynomial to solve this in $$$\mathcal O(\log n)$$$ or $$$\mathcal O(\log^2 n)$$$.
To optimize the second part, we can divide the paths into three types: no end on the extra leaves, one end on the extra leaves, and two ends on the extra leaves. For the first two types, we can simply see the paths as going up and going down so we can enumerate the distance going up and down. Then we can calculate them in $$$\mathcal O(\log^2 n)$$$. For the third part, a dp just like the above will work. The only difference is that only one $$$f_{i,j}$$$ is not $$$0$$$ under this circumstance and we can solve it in $$$\mathcal O(\log^2 n)$$$.
It's also possible to solve this second part in $$$\mathcal O(\log n)$$$ by further optimization of the calculation of the three types of paths.