容斥与反演 反演
设
[F_nsum_{i=0}^{n}A_{n,i}G_i
]
[G_nsum_{i=0}^{n}B_{n,i}F_i
]
下面的直接带入到上面
[F_n=sum_{i=0}^{n}A_{n,i}sum_{j=0}^{i}B_{i,j}F_j=sum_{i=0}^{n}F_isum_{j=i}^{n}A_{n,j}B_{j,i}=F_n
]
设 (C_{i,j}=sum_{k=j}^{i}A_{i,k}B_{k,j})
如果 (C_{i,j}=[i=j])，那么 (F,G) 之间是能够反演的
而 (A,B) 都是下三角矩阵，(C) 就是单位矩阵
知道这个就可以矩阵求逆打表了，而且你发现直接求逆是 (Theta(n^2)) 的
二项式反演
[F_n=sum_{i=0}^n {n choose i}G_iiff G_n=sum_{i=0}^n (-1)^{n-i}{n choose i}F_i
]
证明
[F_n=sum_{i=0}^{n}inom{n}{i}sum_{j=0}^{i}(-1)^{i-j}inom{i}{j}F_j=sum_{i=0}^{n}F_isum_{j=i}^{n}inom{n}{j}inom{j}{i}(-1)^{j-i}
]
[=sum_{i=0}^{n}F_iinom{n}{i}sum_{j=i}^{n}inom{n-i}{j-i}(-1)^{j-i}=sum_{i=0}^{n}F_iinom{n}{i}sum_{j=0}^{n-i}inom{n-i}{j}(-1)^{j}
]
[=sum_{i=0}^{n}F_iinom{n}{i}(1-1)^{n-i}=F_n
]
stirling反演
把第一类Stirling数看成无符号的
[F_n=sum_{i=0}^n egin{Bmatrix} n\i end{Bmatrix}G_iiff G_n=sum_{i=0}^n (-1)^{n-i}egin{bmatrix} n\i end{bmatrix}F_i
]
第一类Stirling数幂与下降幂的关系
[x^{underline k}=sum_{i=0}^k(-1)^{k-i}egin{bmatrix} k\i end{bmatrix}x^i
]
第二类Stirling数幂与下降幂的关系
[x^{k}=sum_{i=0}^kegin{Bmatrix} k\i end{Bmatrix}x^{underline i}
]
反转公式
[egin{cases}sum_{k=m}^n(-1)^{n-k}egin{bmatrix}n\kend{bmatrix}egin{Bmatrix}k\mend{Bmatrix}=[n=m]\sum_{k=m}^n(-1)^{k-m}egin{bmatrix}k\mend{bmatrix}egin{Bmatrix}n\kend{Bmatrix}=[n=m]end{cases}
]
证明
[x^{k}=sum_{i=0}^kegin{Bmatrix} k\i end{Bmatrix}x^{underline i}=sum_{i=0}^kegin{Bmatrix} k\i end{Bmatrix}sum_{j=0}^i(-1)^{i-j}egin{bmatrix} i\j end{bmatrix}x^j
]
[=sum_{i=0}^{k}x^isum_{j=i}^{k}egin{Bmatrix} k\j end{Bmatrix}egin{bmatrix} j\i end{bmatrix}(-1)^{j-i}
]
那么
[sum_{j=i}^{k}egin{Bmatrix} k\j end{Bmatrix}egin{bmatrix} j\i end{bmatrix}(-1)^{j-i}=[i=k]
]
另外一个同理
Min-Max容斥以及kthmax扩展
[max(S)=sum_{Tsubset S}(-1)^{|T|+1}min(T)
]
证明
考虑一种第 (k) 大值被作为最小值计算的次数
[sum_{j=0}^{k-1}(_{j}^{k-1})(-1)^j=(1-1)^{k-1}=[k=1]
]
kthmax
求第 (k) 大元素
构造容斥系数 (f)
使得
[kthmax(S)=sum_{Tsubset S}f(|T|)min(T)
]
考虑第 (x) 大值被作为最小值计算的次数
[sum_{j=0}^{x-1}(_{j}^{x-1})f(j+1)
]
它应该等于 ([x=k])
即
[sum_{j=0}^{x-1}(_{j}^{x-1})f(j+1)=[x=k]
]
二项式反演得到
[f(x)=(-1)^{x-k}(_{k-1}^{x-1})
]
那么
[kthmax(S)=sum_{Tsubset S}(-1)^{|T|-k}(_{k-1}^{|T|-1})min(T)
]