首页 > 牛客推荐系统开发之下班
开通博客写题解
头像 弁财天
发表于 2021-06-11 22:13:43
经典斐波那契套路题，首先你得知道斐波那契数列这样的一个性质。 有了这样一个性质，我们便可以把原式转为： 接下来就是经典的莫比乌斯反演套路了。但不太一样的是，我们需要在这一步打住： 令 ，由于 只有 的不同的取值情况且 可以通过数论分块 求解，根据大佬的结论，暴力求解 这样的函数所有取值情 展开全文
去ta的博客 赞 (4) 回复(3) 收起
头像 范艺杰
发表于 2021-06-11 22:45:02
好像只有我的公式是长这样的，但是跑的最快。 考虑到 其中，*是狄利克雷卷积，I是单位1。进行杜教筛即可。这里提一点，一个函数和mu卷是可以O(n)的求的。 #include <cstdio> #include <cstring> #include <algorithm& 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 Rodriguez
发表于 2021-06-11 22:29:11
先转化问题： 然后考虑计算 的 的个数，并记作 ，这样所求即为： 考虑快速计算 ： 对 和外层和式均整除分块即可，复杂度不高于 。
去ta的博客 赞 (2) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”