310673: CF1868C. Travel Plan
Description
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.
InputThe 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$.
OutputFor each test case output one integer — the sum of scores of all possible travel plans, modulo $998\,244\,353$.
ExampleInput5 3 1 2 2 10 9 43 20 154 147Output
6 19 583217643 68816635 714002110Note
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$.
Output
在高考后的暑假，Tom和Daniel计划去旅行。他们的国家有n个城市，编号从1到n。每个城市i（1≤i≤n）有以下两条路：
- 如果2i≤n，则有一条路连接城市i和2i；
- 如果2i+1≤n，则有一条路连接城市i和2i+1。
Daniel为每个城市选择一个介于1和m之间的整数值，记为ai。
设si,j是城市i和j之间简单路径上的城市的最大值。旅行计划的成绩是所有可能的si,j之和。
Tom想要知道所有可能的旅行计划的成绩之和。你需要帮助Daniel找到这个值，结果对998,244,353取模。
输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤200），表示测试用例的数量。
- 每个测试用例包含一行，有两个整数n和m（1≤n≤10^18，1≤m≤10^5），分别表示城市的数量和城市的最大值。
- 所有测试用例的m之和不超过10^5。
输出：
- 对于每个测试用例，输出一个整数，表示所有可能的旅行计划的成绩之和，对998,244,353取模。
示例：
输入：
5
3 1
2 2
10 9
43 20
154 147
输出：
6
19
583217643
68816635
714002110
注意：
在第一个测试用例中，只有一种可能的旅行计划：
路径1→1: s1,1=a1=1。
路径1→2: s1,2=max(1,1)=1。
路径1→3: s1,3=max(1,1)=1。
路径2→2: s2,2=a2=1。
路径2→1→3: s2,3=max(1,1,1)=1。
路径3→3: s3,3=a3=1。
成绩是1+1+1+1+1+1=6。
在第二个测试用例中，有四种可能的旅行计划：
计划1的成绩：1+1+1=3。
计划2的成绩：1+2+2=5。
计划3的成绩：2+2+1=5。
计划4的成绩：2+2+2=6。
因此，成绩之和是3+5+5+6=19。题目大意： 在高考后的暑假，Tom和Daniel计划去旅行。他们的国家有n个城市，编号从1到n。每个城市i（1≤i≤n）有以下两条路： - 如果2i≤n，则有一条路连接城市i和2i； - 如果2i+1≤n，则有一条路连接城市i和2i+1。 Daniel为每个城市选择一个介于1和m之间的整数值，记为ai。 设si,j是城市i和j之间简单路径上的城市的最大值。旅行计划的成绩是所有可能的si,j之和。 Tom想要知道所有可能的旅行计划的成绩之和。你需要帮助Daniel找到这个值，结果对998,244,353取模。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤200），表示测试用例的数量。 - 每个测试用例包含一行，有两个整数n和m（1≤n≤10^18，1≤m≤10^5），分别表示城市的数量和城市的最大值。 - 所有测试用例的m之和不超过10^5。 输出： - 对于每个测试用例，输出一个整数，表示所有可能的旅行计划的成绩之和，对998,244,353取模。 示例： 输入： 5 3 1 2 2 10 9 43 20 154 147 输出： 6 19 583217643 68816635 714002110 注意： 在第一个测试用例中，只有一种可能的旅行计划： 路径1→1: s1,1=a1=1。 路径1→2: s1,2=max(1,1)=1。 路径1→3: s1,3=max(1,1)=1。 路径2→2: s2,2=a2=1。 路径2→1→3: s2,3=max(1,1,1)=1。 路径3→3: s3,3=a3=1。 成绩是1+1+1+1+1+1=6。 在第二个测试用例中，有四种可能的旅行计划： 计划1的成绩：1+1+1=3。 计划2的成绩：1+2+2=5。 计划3的成绩：2+2+1=5。 计划4的成绩：2+2+2=6。 因此，成绩之和是3+5+5+6=19。