狄利克雷卷积学习笔记

蒟蒻尚在学习,请各位dalao不要相信本文的任何一个字,包括标点符号。


什么是狄利克雷卷积

狄利克雷卷积定义式如下:
$\large f*g(n)=\sum_{d|n}f(d)*g(\frac{n}{d})$
也可以写作:
$\large f*g(n)=\sum_{i*j=n}f(i)*g(j)$


怎么算狄利克雷卷积

单独计算$f*g(n)$

显然我们可以根据定义式暴力计算,枚举$i$即可,复杂度$O(\sqrt{n})$
这里就不上代码了,跟暴力枚举质数长得基本上一模一样。

计算$f*g$

如果再像暴力计算那样,复杂度将达到恐怖的$O(n\sqrt{n})$。
但是我们可以从质数筛(埃塞)的想法入手,我们可以直接枚举一个$i$,再为它的倍数上的值加上对应的贡献就好。时间复杂度$O(nlogn)$。
代码大概长这样w

void Dirichlet(int f[],int g[],int ans[],int n)
{
    memset(ans,0,sizeof ans);
    for(int i=1;i<=n;i++)
        for(int j=1;i\*j<=n;j++)
            ans[i\*j]+=f[i]\*g[j];
}

怎么样,是不是比FFT容易一千万倍?


狄利克雷卷积有什么性质

满足:
1. 交换律
2. 结合律
3. 分配率

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注