A8735 | Flying Saucer Segments
时间限制1s
内存限制256MB
通过 / 提交0/0
题目描述
An expedition group flew from planet ACM-1 to Earth in order to study the bipedal species (its representatives don't even have antennas on their heads!).
The flying saucer, on which the brave pioneers set off, consists of three sections. These sections are connected by a chain: the 1-st section is adjacent only to the 2-nd one, the 2-nd one — to the 1-st and the 3-rd ones, the 3-rd one — only to the 2-nd one. The transitions are possible only between the adjacent sections.
The spacecraft team consists of $n$ aliens. Each of them is given a rank — an integer from $1$ to $n$ . The ranks of all astronauts are distinct. The rules established on the Saucer, state that an alien may move from section $a$ to section $b$ only if it is senior in rank to all aliens who are in the segments $a$ and $b$ (besides, the segments $a$ and $b$ are of course required to be adjacent). Any alien requires exactly $1$ minute to make a move. Besides, safety regulations require that no more than one alien moved at the same minute along the ship.
Alien $A$ is senior in rank to alien $B$ , if the number indicating rank $A$ , is more than the corresponding number for $B$ .
At the moment the whole saucer team is in the 3-rd segment. They all need to move to the 1-st segment. One member of the crew, the alien with the identification number CFR-140, decided to calculate the minimum time (in minutes) they will need to perform this task.
Help CFR-140, figure out the minimum time (in minutes) that all the astronauts will need to move from the 3-rd segment to the 1-st one. Since this number can be rather large, count it modulo $m$ .
The flying saucer, on which the brave pioneers set off, consists of three sections. These sections are connected by a chain: the 1-st section is adjacent only to the 2-nd one, the 2-nd one — to the 1-st and the 3-rd ones, the 3-rd one — only to the 2-nd one. The transitions are possible only between the adjacent sections.
The spacecraft team consists of $n$ aliens. Each of them is given a rank — an integer from $1$ to $n$ . The ranks of all astronauts are distinct. The rules established on the Saucer, state that an alien may move from section $a$ to section $b$ only if it is senior in rank to all aliens who are in the segments $a$ and $b$ (besides, the segments $a$ and $b$ are of course required to be adjacent). Any alien requires exactly $1$ minute to make a move. Besides, safety regulations require that no more than one alien moved at the same minute along the ship.
Alien $A$ is senior in rank to alien $B$ , if the number indicating rank $A$ , is more than the corresponding number for $B$ .
At the moment the whole saucer team is in the 3-rd segment. They all need to move to the 1-st segment. One member of the crew, the alien with the identification number CFR-140, decided to calculate the minimum time (in minutes) they will need to perform this task.
Help CFR-140, figure out the minimum time (in minutes) that all the astronauts will need to move from the 3-rd segment to the 1-st one. Since this number can be rather large, count it modulo $m$ .
输入格式
The first line contains two space-separated integers: $n$ and $m$ $(1<=n,m<=10^{9})$ — the number of aliens on the saucer and the number, modulo which you should print the answer, correspondingly.
输出格式
Print a single number — the answer to the problem modulo $m$ .
输入输出样例
输入 #1
1 10
输出 #1
2
输入 #2
3 8
输出 #2
2
In the first sample the only crew member moves from segment 3 to segment 2, and then from segment 2 to segment 1 without any problems. Thus, the whole moving will take two minutes.
To briefly describe the movements in the second sample we will use value , which would correspond to an alien with rank $i$ moving from the segment in which it is at the moment, to the segment number $j$ . Using these values, we will describe the movements between the segments in the second sample: , , , , , , , , , , , , , , , , , , , , , , , , , ; In total: the aliens need 26 moves. The remainder after dividing $26$ by $8$ equals $2$ , so the answer to this test is $2$ .
To briefly describe the movements in the second sample we will use value , which would correspond to an alien with rank $i$ moving from the segment in which it is at the moment, to the segment number $j$ . Using these values, we will describe the movements between the segments in the second sample: , , , , , , , , , , , , , , , , , , , , , , , , , ; In total: the aliens need 26 moves. The remainder after dividing $26$ by $8$ equals $2$ , so the answer to this test is $2$ .
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？
提交通过
评测结果：Accepted