搜索结果
查询Tags标签： 反演，共有 17条记录-
任意长度循环卷积&单位根反演 学习笔记
今天听 \(\texttt{m}\color{red}{\texttt{yee}}\) 嘴的，赶紧来补个学习笔记。 PS：FFT 本质是长度为 \(2^k\) 的循环卷积。 单位根反演 反演本质： \[\frac1n\sum_{i=0}^{n-1}\omega_{n}^{ai}=[n|a] \]证明：如果 \(n|i\)，那么显然可以将 \(a\) 拆为若干个 \(\omega_n^n…
2022/8/6 23:26:21 人评论 次浏览 -
二项式反演
二项式反演 定理 \(1\)：\(F(n)=\sum_{i=0}^{n}{{n\choose i}G(i)}\Leftrightarrow G(n)=\sum_{i=0}^{n}{(-1)^{n-i}{n\choose i}F(i)}\) 证明： 提取系数有 \(F[n]=\sum_{i=0}^{n}{{n\choose i}G[n]}\) \(\displaystyle \to \frac{F[n]}{n!}=\sum_{i=0}^{n}{\frac{1}{(n-…
2022/7/24 6:25:17 人评论 次浏览 -
BSOJ5532题解
大朋友与多叉树 首先可以列出来这个： \[F(x)=x+\sum F^{d_i}(x) \]于是设： \[G(x)=\sum x^{d_i} \]\[F(x)=x+G(F(x)) \]\[F(x)-G(F(x))=x \]设 \(H(x)=x-G(x)\)，就有 \(H(F(x))=F(H(x))=x\)，根据拉格朗日反演就有： \[[x^n]F(x)=\frac{1}{n}[x^{n-1}](\frac{H(x)}{x})…
2022/7/9 23:24:11 人评论 次浏览 -
莫比乌斯反演自我击毙进程1-1
前情提要：关于莫比乌斯翻译，是真的懵逼吾死，莫比乌斯函数（好理解），狄利克雷卷积（能懂不会用），莫比乌斯反演（队友泪两行），杜教筛（呵呵），因为看了两天自己不能自理的推出来，所以写个博客帮助下理解，懂了就改。。。。。。。 需要提前知道的知识： 积性函数：…
2022/7/6 5:20:36 人评论 次浏览 -
重修 二项式反演
我只知道容斥不知道二项式反演。 反演，顾名思义就是有两个函数 \(f,g\)，知道 \(f\) 用 \(g\) 表示后反过来 \(g\) 用 \(f\) 表示。 二项式反演有一个无敌对称的柿子： \[f(n)=\sum_{i=1}^n(-1)^i\binom{n}{i}g(i)\iff g(n)=\sum_{i=1}^n(-1)^i\binom{n}{i}f(i) \]这个柿…
2022/6/21 23:19:45 人评论 次浏览 -
基于MERSI-II的中国积雪覆盖度反演(MESMA-AGE)进展-Part-1 : 数据更新和展示
写在前面这是我的第一篇博客，仅供个人实验记录。不定期更新，主要看自己卷不卷得动，卷不动了就写写。PS.五月诸事不顺，希望接下来的六月待我温柔！ 一. 数据介绍使用到的光学卫星数据为MERSI地表反射率数据，为中科院提供的部分测试数据。该数据经过了辐射校正、地理配…
2022/5/28 23:21:25 人评论 次浏览 -
数论分块、杜教筛思想、莫比乌斯反演初探
1 1.对于L,R；2 找到最大的R，使得[n/l]=[n/r];3 n/r>=[n/r]-->r<=n/[n/r] 4 <<=>>5 r<=n/[n/l];6 7 2.8 [[n/x]/y]=[n/xy]9 10 3.杜教筛 11 i >= 1 && i <= n j >= 1 && j <= n 12 求它们的互质对数 13 令f(n)=它…
2022/4/10 23:13:09 人评论 次浏览 -
一些公式和定理
公式＆定理：两个互为反演的关系矩阵互逆二项式反演 1 \(\large F(n) = \displaystyle\sum_{i=0}^{n} (-1)^i \binom{n}{i} G(i) \Longleftrightarrow G(n)=\sum_{i=0}^{n}(-1)^i \binom{n}{i}F(i)\)二项式反演 2（对于形式1进行基本反演推论的应用） \(\large F(n) = \di…
2022/3/27 6:52:35 人评论 次浏览 -
学习知识点链接
学了一些比较好的博客，在这边记录一下。不定期更新，学了新的知识点就来这边更新一下。 1、吉司机线段树 学习博客1 搭配里面的练习题+模板题洛谷线段树3练习更好。 学习博客2 两篇博客结合食用，两边的例题在对于lazy标记的操作上是不同的，可以学习一下。 2、博弈论 一…
2021/9/2 23:07:50 人评论 次浏览 -
学习知识点链接
学了一些比较好的博客，在这边记录一下。不定期更新，学了新的知识点就来这边更新一下。 1、吉司机线段树 学习博客1 搭配里面的练习题+模板题洛谷线段树3练习更好。 学习博客2 两篇博客结合食用，两边的例题在对于lazy标记的操作上是不同的，可以学习一下。 2、博弈论 一…
2021/9/2 23:07:50 人评论 次浏览 -
二项式反演入门
对于序列 \(\{f_n\}\) 和 \(\{g_n\}\)，通过 \(f\) 计算出 \(g\) 叫做正演，通过 \(g\) 计算出 \(f\) 叫做反演。 形式 二项式反演讲的是： \[g_n=\sum_{i=0}^n\binom{n}{i}f_i \Leftrightarrow f_n=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}g_i \]证明 将组合数展开得到： \[\…
2021/8/8 23:39:06 人评论 次浏览 -
二项式反演入门
对于序列 \(\{f_n\}\) 和 \(\{g_n\}\)，通过 \(f\) 计算出 \(g\) 叫做正演，通过 \(g\) 计算出 \(f\) 叫做反演。 形式 二项式反演讲的是： \[g_n=\sum_{i=0}^n\binom{n}{i}f_i \Leftrightarrow f_n=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}g_i \]证明 将组合数展开得到： \[\…
2021/8/8 23:39:06 人评论 次浏览 -
康复训练+To Do List
模板： 字符串:[ ] Sa+O(1)height [ ] Sam+线段树合并 [ ] 广义Sam [ ] kmp [ ] ac自动机 [ ] Pam [ ] Manacher筛法[ ] 莫比乌斯反演 [ ] 线筛筛一般函数 [ ] 狄利克雷卷积及某些函数的性质 [ ] 杜教筛 [ ] min_25筛多项式[ ] fft,ntt,mtt [ ] 多项式全家桶（下降幂，插值…
2021/7/27 23:35:54 人评论 次浏览 -
康复训练+To Do List
模板： 字符串:[ ] Sa+O(1)height [ ] Sam+线段树合并 [ ] 广义Sam [ ] kmp [ ] ac自动机 [ ] Pam [ ] Manacher筛法[ ] 莫比乌斯反演 [ ] 线筛筛一般函数 [ ] 狄利克雷卷积及某些函数的性质 [ ] 杜教筛 [ ] min_25筛多项式[ ] fft,ntt,mtt [ ] 多项式全家桶（下降幂，插值…
2021/7/27 23:35:54 人评论 次浏览 -
P3327 [SDOI2015]约数个数和（莫比乌斯反演）
题目描述： 设\(d(x)\)为\(x\)的约数个数，给定\(n,m\)，求\(\sum_{i=1}^n\sum_{j=1}^md(ij)\) 首先有一个前置知识： \(d(ij)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]\) 所以原式等于： \(\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]\) 反演以下： \(\sum_{i=1…
2021/7/13 6:09:09 人评论 次浏览
