大凤号装甲空母【找规律+矩阵快速幂】

大凤号装甲空母
时间限制: 1 Sec 内存限制: 128 MB
提交: 108 解决: 15
[提交] [状态] [命题人:admin]
题目描述
大凤号航空母舰很喜欢算术。
它，是旧日本海军中最为先进的航空母舰。
它，是旧日本海军中最为短命的航空母舰。
同时，她还是最平的航空母舰（龙骧：你说啥？）
如此多第一 ……
一生二，二生三，三生万物 ……
这也许就是大凤喜欢算术的原因吧。
有一天，她看到了这样一道题：
令
电探发现了来自远处的鱼雷，时间不多了。

输入
一行由空格隔开的两个非负整数，分别是n和p。

输出
一行表示答案。

样例输入
复制样例数据
5 97
样例输出
11

提示
时间限制: 1 Sec 内存限制: 128 MB
提交: 108 解决: 15
[提交] [状态] [命题人:admin]
题目描述
大凤号航空母舰很喜欢算术。
它，是旧日本海军中最为先进的航空母舰。
它，是旧日本海军中最为短命的航空母舰。
同时，她还是最平的航空母舰（龙骧：你说啥？）
如此多第一 ……
一生二，二生三，三生万物 ……
这也许就是大凤喜欢算术的原因吧。
有一天，她看到了这样一道题：
令
电探发现了来自远处的鱼雷，时间不多了。

输入
一行由空格隔开的两个非负整数，分别是n和p。

输出
一行表示答案。

样例输入
复制样例数据
5 97
样例输出
11

提示

解题思路：
通过打表，得

可以推出对于 ⌊ x n ⌋ \lfloor x^n \rfloor ⌊xn⌋的值$dp[n]$满足：
$dp[n]=f[n]+f[n-2]$即$dp[n]=f[n-1]+2$

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！