首页 > 其他分享 >莫比乌斯反演学习笔记

莫比乌斯反演学习笔记

时间:2023-07-06 10:14:44浏览次数:31  
标签:matrix 卷积 乌斯 sum 反演 莫比

狄利克雷卷积

对于两个数论函数 $f(x)$ 和 $g(x)$,他们的卷积结果 $h(x)$ 定义为

$h(x)=\sum_{d|x}^{}f(d)g(\frac{x}{d} )=\sum_{ab=x}^{}f(a)g(b)  $

即 $h=f*g$

满足交换律,结合律,分配律。

莫比乌斯函数

 

$$\mu (n)=\left\{\begin{matrix}1  &n=1 \\0  & n含有平方因子\\(-1)^{k}   & k为n的本质不同因子个数\end{matrix}\right.$$

 

标签:matrix,卷积,乌斯,sum,反演,莫比
From: https://www.cnblogs.com/DongPD/p/17531307.html

相关文章

  • 莫比乌斯函数入门
    莫比乌斯函数入门之前遇到过很多次莫反的题,但是每次做完就忘了,云里雾里,所以写一篇来好好记忆一下,下次再忘了就回来看看。内容和OIWIKI有很大部分的重叠,但是更偏向结论和做法,同时舍弃了一些看不懂的。莫比乌斯函数定义:\[\mu(n)=\begin{cases}1&n=1\\0&n含有平方因子(......
  • 二项式反演和 Min-Max 反演小记
    二项式反演本质上是某种容斥。结论为:\[f_i=\sum_{j=0}^i(-1)^j\binom{i}{j}g_j\Leftrightarrowg_i=\sum_{j=0}^i(-1)^j\binom{i}{j}f_j\]更常用的形式是\[f_i=\sum_{j=0}^i\binom{i}{j}g_j\Leftrightarrowg_i=\sum_{j=0}^i(-1)^{i-j}\binom{i}{j}f_j\]证明第二个......
  • [数论]数论函数/莫比乌斯反演
    数论函数/莫比乌斯反演1.1积性函数数论函数:可以认为是定义在整数上的函数。1)积性函数定义(a,b)=1,f(a,b)=f(a)f(b)2)积性函数性质对于积性函数\(f\),是被所有\(p^e\)处的值决定的a=1,f(b)=f(1)f(b)​ \(f(60)=f(4)\timesf(15)=f(4)\timesf(3)\timesf(5......
  • fluent中的阿仑尼乌斯公式
    公式介绍阿伦尼乌斯公式(Arrheniusequation)是由瑞典的阿伦尼乌斯所创立的化学反应速率常数随温度变化关系的经验公式。公式写作$$k=AT^\betaexp(−Ea/RT)$$特别需要说明这个公式的单位:k为反应速率R为摩尔气体常数或通用气常数或普适气体常数,其值为8.314J/(mol·K)T为热力......
  • 莫比乌斯反演 学习笔记
    炫酷反演魔术!莫反会用到的具体性质证明先不写,先写题。与其说是学习笔记,不如说是简要的题解集合。不太想贴太多代码啊,翻起来很烦。P3455[POI2007]ZAP-Queries很基础的一道题。令\(a\leb\),考虑\(k=1\)的情况。\[\begin{aligned}ans&=\sum\limits_{i=1}^a\sum\limits_{j=......
  • bzoj 2839. 集合计数 二项式反演
    集合计数设fi表示恰好交集为k的方案数。设gi表示交集至少为k的方案数。\(g_i=\sum_{j=i}^{n}C(j,i)f_j\)由二项式反演得:\(f_k=\sum_{i=k}^{n}(-1)^{i-k}C(i,k)g_i\)考虑\(g_i\)的求出,钦定\(i\)个数必选那么剩下\(n-i\)个数每个数可选可不选\(2^{n-i}\)但这道题我们选出的......
  • SolidWorks软件三维建模教程——莫比乌斯环建模案例
    SolidWorks是达索系统(DassaultSystemes)下的子公司,专门负责研发与销售机械设计软件的视窗产品。SOLIDWORKS软件三维建模功能强大,为制造型企业提供SOLIDWORKS一体化解决方案和服务。今天微辰三维就以莫比乌斯环的三维建模案例,为您提供详细的SolidWorks软件三维建模教程。一起来看如......
  • P4859 已经没有什么好害怕的了 二项式反演
    这道题给出两个数组且每个数字都不同。要求两两配对,这样每一个配对都有一个大小关系。要求第一组大的个数比第二组大的恰好k个配对。显然一共有\(n\)个大小关系,那么容易想到\(n-k\)必然是一个偶数才会有对应方案。那么题目其实是要求第一组比第二组大的个数恰好为\(k+\frac{n-k......
  • [MtOI2019]幽灵乐团 / 莫比乌斯反演基础练习题
    [MtOI2019]幽灵乐团/莫比乌斯反演基础练习题题目描述东风谷早苗(KochiyaSanae)非常喜欢幽灵乐团的演奏,她想对她们的演奏评分。因为幽灵乐团有\(3\)个人,所以我们可以用\(3\)个正整数\(A,B,C\)来表示出乐团演奏的分数,她们的演奏分数可以表示为\[\prod_{i=1}^{A}\prod_......
  • P5518 [MtOI2019]幽灵乐团 / 莫比乌斯反演基础练习题
    简要题意计算\[\prod_{i=1}^{A}\prod_{j=1}^{B}\prod_{k=1}^{C}\left(\frac{\text{lcm}(i,j)}{\gcd(i,k)}\right)^{f(type)}\]其中:\[\begin{aligned}f(0)&=1\crf(1)&=i\timesj\timesk\crf(2)&=\gcd(i,j,k)\end{aligned}\]\(T\)组数据,每......