VISA OA 跪经

刚刚做完VISA的OA，感觉跪了。我收到的是SWE master/PHD。OA的第三题和地里的面经不太一样

您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

AcceleratorLV5 发表于 2018-10-2 04:19
1

那大概只能快速幂了..

我觉得也是dp啊～就是dp[n] = dp[n-1] + dp[n-3] O(n)复杂度啊

z130640637 发表于 2018-10-1 05:24
我觉得也是dp啊～就是dp[n] = dp[n-1] + dp[n-3] O(n)复杂度啊

这题dp过不了是么？

我是用暴力解法过的，我的贴子有位老哥说mod速度比较慢，用减法能过

可以用矩阵乘法的形式来写表达式，然后用快速幂做到log级别。
不过不是太可能出在oa里面，n的范围是多少啊。

fsq19474 发表于 2018-10-2 00:59
可以用矩阵乘法的形式来写表达式，然后用快速幂做到log级别。
不过不是太可能出在oa里面，n的范围是多少啊 ...

1<=n<=10^9，应该没记错

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies