数论小节

做个备忘录把……

二项式反演：

令(f_i)表示至少选择(i)个，(g_i)表示敲好选择(i)个

(f_i=sum_{j=0}^i dbinom{n}{j}*g_j)

(g_i=sum_{j=0}^{i}(-1)^{i-j}dbinom {n}{j}f_j)

范德蒙德卷积:

(dbinom{n}{k}=sum_{i=0}^kdbinom{m}{i}*dbinom{k-i}{n-m})

组合数无名公式：

(dbinom{m}{i}*dbinom{i}{j}=dbinom{m}{j}*dbinom{m-j}{i-j})

中国剩余定理：

(M_i=lcm/m_i, x_i=M_i^{-1}(mod m_i))

(Ans=sum_{i=1}^n x_i*a_i*M_i(mod lcm))

第二类斯特林数：

(S(n, m)=dfrac{1}{m!}*sum_{k=0}^m(-1)^k*dbinom{m}{l}*(m-k)^n)

(n^k=sum_{i=0}^kS(k, i) * i! *dbinom{n}{i})

康拓展开：

(sum_{i=1}^n(s_i-sum_{j=1}^{i-1}[s_j<s_i])*(n-i+1)!)

拉格朗日插值：

(f(k)=sum_{i=0}^ny_i* prod_{i!=j}dfrac{k-x_j}{x_i-x_j})

多重集合排列

设S是多重集合，他有k种不同类型的对象，每一种类型的有限重复数是(n1，n2，n3，…nk)。设S的大小为(n=n1+n2+n3+…nk)。则S的n排列数目为(dfrac{n!}{n1!n2!n3!…nk!})