A16248 | Travel Plan
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
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.
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.
输入格式
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$ .
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$ .
输出格式
For each test case output one integer — the sum of scores of all possible travel plans, modulo $998\,244\,353$ .
输入输出样例
输入 #1
5 3 1 2 2 10 9 43 20 154 147
输出 #1
6 19 583217643 68816635 714002110
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$ .
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$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted