2024-12-12 10:54 已编辑山东大学 C++ 发布于山东

关注

题解 | #莫比乌斯反演与傅里叶变换#

首先，

$\sum_{i=1}^{n}\sum_{j|i}f(j) = \sum_{j=1}^{n}f(j)\sum_{i=1}^{n}[j|i] = \sum_{j=1}^{n}f(j)\cdot \lfloor \frac{n}{j}\rfloor$ .

所以考虑数论分块，试图在允许的时间内求 $f(j)$ 的前缀和，即求

$\sum_{j=0}^{i}f(j)$ ，为了让后面的式子更简洁，这里从0开始求和。

因为 $f$ 是一个 $m-1$ 次多项式，所以 $f$ 的前缀和是一个 $m$ 次多项式，我们可以使用拉格朗日插值，先求 $m+1$ 个位置的前缀和，然后插出任意位置的前缀和。

考虑拉格朗日插值公式

$f(x)=\sum_{i=1}^{n}\prod_{j=1,j\ne i}^{n}\frac{x-x_j}{x_i-x_j}y_i$

其中 $x_i, y_i$ 是所求函数图象上的 $n$ 个点。我们需要 $m+1$ 个点，不妨取 $i=0,\dots, m$ 时的前缀和，记为 $pre[0], \dots, pre[m]$ ，要插的函数

$pre(x)=\sum_{i=0}^{m}\prod_{j=0, j\ne i}^{m}\frac{x-j}{i-j}pre[i]$

被求和的每一项系数的分子和分母都是一些连续整数的乘积，可以用两个数的阶乘相除快速求得，而阶乘和阶乘的逆元可以预处理。

我的代码

全部评论

推荐最新楼层

裁空

山东大学

数论分块好强

点赞回复分享

发布于 06-22 13:32 山东

想成为rating_n

济南大学人工智能

其实我推出过另一个式子，但无法在log(n)时间复杂度求解 1^x+2^x+3^x+...+n^x式子的解法，请问有什么好的解法嘛？

点赞回复分享

发布于 2024-12-17 18:18 山东

09-28 20:59

门头沟学院 Java

pdd 9.20 线下面经

背景：后端开发 部门没定 9.20线下 三轮技术面+一轮hr面 从9点面到下午1点多9.25早晨电话沟通，9.25晚上收到意向技术面问题（汇总版）没有单独问八股，都是边聊简历上的内容边拓展问八股mvcc底层实现innodb引擎分布式事务-二阶段提交-mysql xa-spring框架的二阶段提交事务相关问题手撕 二叉搜索树的定位场景 如果给你一张表 只有三个字段 自增主键id 学生姓名 手机号码 实现抽奖功能

查看6道真题和解析

点赞评论收藏

09-29 14:58

河北师范大学人力资源专员/助理

深信服线下面(AI开发 )

一站式面试，可惜倒在了二面完全没有问八股，也没有手撕，纯问项目，深挖着问，发散着问，问的人汗流浃背.二面基本是边聊天边问，发散性的问题很多，看着二面面试官和我笑嘻嘻，我就觉得情况不妙，果然给我挂了，可能是一面项目答得不太好

发面经攒人品

点赞评论收藏

09-16 17:33

已编辑

哈尔滨商业大学 Java

大佬们帮我看看27届找日常的第一份简历需要怎么改

27届双非想找日常实习，还没开始投，高频的八股都背了一点，想开始边投边背了，简历那里需要改动吗，还是接着沉淀等春招再找实习，因为我算法题没怎么学过，想着先找小厂实习不知道可行吗。

实习，投递多份简历没人回...

点赞评论收藏

09-08 16:30

济南大学后端工程师

求佬们给一下建议

27毕业想找第一段日常实习，简历有什么需要优化的吗

星期一的大老师：项目描述和技术栈单开一栏；八股文：算法与数据结构，计算机网络一定要写，操作系统不了解可以不写；Linux命令，Git，Docker基础命令和基本使用一定要写，要有实际使用场景的解决经验；项目的八股文上：redis 解决缓存雪崩，缓存击穿，缓存穿透的解决方案，一个问题的不同方案可以一起用，不需要重复在两个项目写。第二个项目换一个。小厂可以投一投