弁财天

2021-06-11 22:17 已编辑广州大学 C++

关注

题解 | #牛客推荐系统开发之下班#

牛客推荐系统开发之下班

https://ac.nowcoder.com/acm/contest/11174/F

经典斐波那契套路题，首先你得知道斐波那契数列这样的一个性质。

$\gcd(f_n,f_m)=f_{\gcd(n,m)}$

有了这样一个性质，我们便可以把原式转为：

$\sum\limits_{i_1=1}^n\sum\limits_{i_2=1}^n\sum\limits_{i_3=1}^n\cdots\sum\limits_{i_k=1}^nf_{\gcd(i1,i2,i3,\cdots,i_n)}$

接下来就是经典的莫比乌斯反演套路了。但不太一样的是，我们需要在这一步打住：

$\sum\limits_{d=1}^nf_d\sum\limits_{t=1}^{\lfloor\frac{n}{d}\rfloor}\mu(t)\lfloor\frac{n}{dt}\rfloor^k$

令 $g(n)=\sum\limits_{t=1}^n\mu(t)\lfloor\frac{n}{t}\rfloor^k$ ，由于 $g(n)$ 只有 $O(\sqrt n)$ 的不同的取值情况且 $g(n)$ 可以通过数论分块 $O(\sqrt n)$ 求解，根据大佬的结论，暴力求解 $g(n)$ 这样的函数所有取值情况时间复杂度貌似是 $O(n^{\frac{3}{4}})$ （反正跑得飞快）。现在只需要关注 $f_d$ 的前缀和就行。还好这里还有个关于斐波那契数列前缀和 $S_n$ 的公式：

$S_n=f_{n+2}-1$

这下将问题转移为单点求斐波那契数列的问题了。考虑 $f_n$ 的通项公式：

$f_n=\frac{1}{\sqrt 5} [(\frac{1+\sqrt 5}{2})^n-(\frac{1-\sqrt 5}{2})^n]$

因为 $5$ 是模 $1e9+9$ 的二次剩余，说明 $\sqrt 5$ 在模 $1e9+9$ 下存在意义。不会求二次剩余也不是很大问题，本地暴力求出即可，得到其中一个解为 $616991993$ ，即可以用 $616991993$ 替换原式中的 $\sqrt 5$ ，那么此时原式就可以进行数论分块了。总的复杂度为 $O(n^{\frac{3}{4}})$ 。

全部评论

推荐最新楼层

Mark_Sun

山东大学 Java

那你为什么只A了一道题？

点赞回复分享

发布于 2021-06-11 22:17

Nanarikom

哈尔滨工程大学 Java

请问为什么分块套分块是 O(n^{\frac{3}{4}}) 的啊，能给个证明链接啥的吗 ;w;

点赞回复分享

发布于 2021-06-11 23:37

弁财天

楼主

广州大学 C++

这个n^0.75的复杂度我也是从洛谷幽灵乐团那里的题解云来的。。。希望有大佬能给出时间复杂度分析

点赞回复分享

发布于 2021-06-12 00:18

02-11 14:12

内蒙古艺术学院游戏策划

多益网络游戏运营-一面面经

如果你负责一款新上线的 MMORPG 游戏，如何在前期吸引大量玩家并保持他们的活跃度？针对不同年龄段和性别，你认为游戏运营策略应该有哪些不同？谈谈你对当前热门游戏《原神》的运营模式的理解，有哪些值得借鉴的地方？假如游戏内出现玩家大量流失的情况，你会从哪些方面去分析原因并提出解决方案？游戏运营中，如何平衡付费玩家和免费玩家的游戏体验？请举例说明你了解的一种游戏社区运营方法，并阐述其对游戏运营的作用。对于游戏中的外挂问题，你认为应该采取哪些措施来有效打击？未来元宇宙概念可能会对游戏运营产生重大影响，你认为我们该如何提前布局？

查看8道真题和解析非技术面试记录

点赞评论收藏

02-15 20:16

已编辑

中国矿业大学 C++

手撕线程池-学习C++11

目的学习C++11的部分特性清晰手撕代码时的思考过程阅读顺序需要了解的C++11特性：template 模板...Args 可变类型参数STL emplace、emplace_back 容器操作方法Lambda 表达式std::move 移动语义、std::forward 完美转发std::shared 智能指针、std::thread C++多线程std::future、std::promise 线程执行的结果传递std::mutex、std::condition_variable 互斥量与条件变量std::function、std::bind、std::packaged_task 函数封装...

点赞评论收藏

2024-12-29 11:08

湖南工业大学 Java

26届简历求指导

程序员牛肉：简历没什么大问题了。而且不要再换项目了。三月份就开暑期实习了，现在都一月份了。实在来不及重新开一下项目了。把一个项目写完或许很快，但是把一个项目搞懂吃透并不简单。所以不要换项目了，把你简历上面的两个项目好好挖一挖吧。具体体现在：你能不能流利的说出你的项目的每一个功能点代码实现？你能不能说出在这块除了A技术之外，还有其他技术能够实现嘛？如果有其他技术能够实现，那你这块为什么选择了你当前用的这个技术？

投递牛客等公司10个岗位