CF 643G Choosing Ads(线段树)
Luogu P2824 [HEOI2016/TJOI2016]排序(线段树,二分答案)
CF 997C Sky Full of Stars(二项式反演,DP)
二项式反演
主要形式 形式一 $$f(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}g(i)\quad\Longleftrightarrow\quad g(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}f(i)$$ 形式二 $$f(n)=\sum\limits_{i=0}^n\dbinom{n}{i}g(i)\quad\Longleftrightarrow\quad g(n)=\sum\limits_{i=0}^n(-1)^{n-i}\dbinom{n}{i}f(i)$$ 形式三 $$f(n)=\sum\limits_{i=n}^m(-1)^i\dbinom{i}{n}g(i)\quad\Longleftrightarrow\quad g(n)=\sum\limits_{i=n}^m(-1)^{i}\dbinom{i}{n}f(i)$$ 形式四 $$f(n)=\sum\limits_{i=n}^m\dbinom{i}{n}g(i)\quad\Longleftrightarrow\quad g(n)=\sum\limits_{i=n}^m(-1)^{i-n}\dbinom{i}{n}f(i)$$ 证明 反演基本形式如下 $$f(n) = \sum\limits_{i=0}^n{a_i}g(i)$$ $$g(n) = \sum\limits_{i=0}^n{b_i}f(i)$$ 在形式一中,有 $a_i = b_i = (-1)^i\dbinom{n}{i}$ 要证 $$f(n)=\sum\limits_{i=0}^na_ig(i)\Longrightarrow g(n)=\sum\limits_{i=0}^nb_if(i)$$ 只要证 $$g(n)=\sum\limits_{i=0}^nb_if(i)=\sum\limits_{i=0}^nb_i\sum\limits_{j=0}^ia_jg(j) = \sum\limits_{j=0}^ng(j)\sum\limits_{i=j}^nb_ia_j$$ 只要证 $$\sum\limits_{i=j}^nb_ia_j=[j=n]$$ 只要证 $$\sum\limits_{i=j}^n(-1)^i\dbinom{n}{i}\times(-1)^j\dbinom{i}{j}=[j=n]$$