莫比乌斯反演

\(\texttt{updating……}\)多项式复合对于多项式\(F(x),G(x)\)，其复合为:\(F(G(x))=\sum_{i}[x^i]F(x)G(x)^i\)求法：设\(B=\sqrtn\)\[\begin{aligned}\sum_{i=0}^n[x......

这是两个本质不同的东西。多步容斥是“至少或至多选若干个”到“恰好选若干个”的变换。而二项式反演是“钦定选若干个”到“恰好选若干个”的变换。二项式反演虽然形式上......

前言本文用集合的符号表示二进制数。具体地，定义全集\(u\)是\(2^n-1\)，某个二进制数\(x\)第\(t\)位是1可以理解为为\(x\)中有\(t\)号元素，否则没有。定义\(|x|......

前置知识多项式基础快速傅里叶变换/数论变换（FFT/FNTT）位运算（集合运算）引入·位运算卷积典型的FFT,NTT被用于解决加法卷积问题。具体地，它可以解决的基本问题是：给......

本文大量参考了：《反演与筛法》马耀华OI中（？）常用数论函数求和法的大致描述、zzt求和法的简化版，negiizhao1积性函数与反演我们先给出一些关于数论函数的基本定义。......

\(\textbf{QAQ}\)令\(h\)为两个数论函数\(f,g\)的Dirichlet卷积\(f*g\)，则\[h(n)=\sum_{d|n}f(d)g(\frac{n}{d})\]它满足结合律，交换律，分配律。Dirichlet卷积单......

tobefix:“扩展”部分的式子是假的二维子集反演莫比乌斯反演容斥原理&莫比乌斯反演一、函数卷积：定义函数卷积\(f(x,y)\)和\(g(x,y)\)是\(X\timesX\ri......

1、积性函数2、欧拉筛求积性函数3、莫比乌斯反演4、狄拉克雷卷积......

\[C_k=\sum_{i|j=k}A_iB_j\]这样的或卷积可以做一次\(\text{FWT}\)，把数组变为\(a_i=\sum_{j\subseteqi}A_i\)，也就是子集和的形式，然后就可以对应位相乘了变回去的......

记录一些自己做的简单题。P6478简单容斥。设\(f[x][i]\)表示\(x\)为根子树，钦定\(i\)对祖孙关系的方案数。可以用树形背包转移。（顺便给我科普了真正正确的树形背包......