待更新
計數原理
加法原理
又稱分類計數原理
完成一個作業共有\(n\)類方法，在第一類方法中有\(m_1\)種不同的方法，在第二類方法中有\(m_i\)種不同的方法，……，在第\(n\)類方法中有\(m_n\)種不同的方法，那么完成這個作業共有\(m_1+m_2+……+m_n\)種不同的方法，
乘法原理
又稱分步計數原理
完成一件作業共需\(n\)個步驟，完成第一個步驟有\(m_1\)種方法，完成第二個步驟有\(m_2\)種方法，……，完成第\(n\)個步驟有\(m_n\)種方法，那么完成這個作業共有\(m_1\times m_2\times…\times m_n\)種方法，
排列組合
排列數
用\(A_n^m\)表示從\(n\)個不同元素中依次取出\(m\)個元素排成一列，產生的不同排列的數量
\(A_n^m=\dfrac{n!}{(n-m)!}=n\times (n - 1) \times(n-2)\times…\times(n-m+1)\)
組合數
用\(C_n^m\)或\(\dbinom{n}{m}\)表示從\(n\)個不同元素種取出\(m\)個組成一個集合（不考慮順序），產生的不同集合的數量
\(\dbinom{n}{m}=\dfrac{n!}{m!(n-m)!}=\dfrac{n\times(n-1)\times…\times(n-m+1)}{m\times(m-1)\times…\times2\times1}\)
組合恒等式
證明百年之后補
- \(\dbinom{n}{m}=\dbinom{n}{n-m};\)
- \(\dbinom{n}{m}=\dbinom{n-1}{m-1}+\dbinom{n-1}{m}\)
- \(\sum\limits_{i=0}^{n}\dbinom{n}{i}=2^n;\)
- $\sum\limits_{i=0}^{n}\dbinom{n}{i}[2\mid i]=\sum\limits_{i=0}^{n}[2\nmid i]=2^{n-1} $
- \(k\)個非負整數變數和為\(n\)的方案數（插板法）：\(\dbinom{n+k-1}{k-1}\)
- \(\sum\limits_{i=0}^m\dbinom{n+i}{n}=\dbinom{n+m+1}{m}\)
- \(\sum\limits_{i=m}^n\dbinom{i}{m}=\dbinom{n+1}{m+1}\)
- \(\dbinom{n}{m}\dbinom{m}{k}=\dbinom{n}{k}\dbinom{n-k}{m-k}\)
- \(\sum\limits_{i=0}^k\dbinom{n}{i}\dbinom{m}{k-i}=\dbinom{n+m}{k}\)
二項式定理
\((x+y)^n=\sum\limits_{k=0}^n\dbinom{n}{k} x^ky^{n-k}\)
自然數冪之和
\[S_k(n)=\sum\limits_{i=1}^ni^k \]
小結論
\(S_k(n)\)是關于\(n\)的\(k+1\)次多項式，
歸納&&證明
對\(k\)歸納：
- \(k=0,S_k(n)=n\)，是關于\(n\)的一次多項式
- \(k\leq d-1\),是關于\(n\)的\(d\)次多項式
前置：諤項式定理
\(\ \ \ (i+1)^{d+1}-i^{d+1}\\=\sum\limits_{j=0}^{d+1}\dbinom{d+1}{j}i^j-i^{d+1}\\=\sum\limits_{j=0}^d\dbinom{d+1}{j}i^j\)
然而上面這些并沒有用，這樣并不能求出\(S_k(n)\)的值，所以考慮再加一層求和符號（因為可以交換/cy）
\(\ \ \ \sum\limits_{i=1}^{n}((i+1)^{d+1}-i^{d+1})\\=\sum\limits_{i=1}^n\sum\limits_{j=0}^d\dbinom{d+1}{j}i^j\\=\sum\limits_{j=0}^d\dbinom{d+1}{j}\sum\limits_{i=1}^ni^j\\=\sum\limits_{j=0}^d\dbinom{d+1}{j}S_j(n)\)
上面那個\(\sum\limits_{i=1}^{n}((i+1)^{d+1}-i^{d+1})\)其實又等于\((n+1)^{d+1}-1\)
所以現在我們就得到了\((n+1)^{d+1}-1=\sum\limits_{i=0}^d\dbinom{d+1}{i}S_i(n)\)
把\(S_d(n)\)提出來再除一下，胡亂化一下就能發現\(S_d(n)\)的確是\(n+1\)次的多項式……得證（因為懶所以不想寫了，而且是小學知識……）
求法
暴力
\(O(n\log k)\)
rank1，呼呼呼，好快
拉格朗日插值
待補充
對于\(k\)次多項式函式\(\mathbf F\)以及\(k+1\)個點值\((x_0,y_0),(x_1, y_1),...,(x_k, y_k)\)，有\(\mathbf F(x)=\sum\limits_{i=0}^jy_i\prod\limits_{i\ne j}\dfrac{x-x_j}{x_i-x_j}\)
可以做到\(O(k\log k)\)
局限性：模數必須是大于\(n\)的質數
斯特林數
\(S_k(n)=\dfrac{(n+1)^{\underline{k+1}}}{k+1}-\sum\limits_{i=0}^{k-1}(-1)^{k-i}\cdot\begin{bmatrix}k\\i\end{bmatrix}\cdot S_i(n)\)
證明
一個組合恒等式（先不講為啥）：
\[n^{\underline{k}} = \sum_{i=0}^{k}(-1)^{k-i}{ \left[{\begin{matrix}k\\i\end{matrix}}\right]}n^{i} \]
其中\(n^{\underline k}\)表示\(n\)的\(k\)次下降冪
我們一般的\(n^k\)是\(k\)個\(n\)相乘，但是這里是每次乘都減一
展開就是\(n\times(n-1)\times(n-2)…\times(n-k+1)\)
\(i=k\) 時，有 \((-1)^{k-i} \begin{bmatrix}k\\i\end{bmatrix} n^i=n^k\)，則
\[n^k = n^{\underline{k}} - \sum\limits_{i=0}^{k-1}(-1)^{k-i}{ \left[{\begin{matrix}k\\i\end{matrix}}\right]}n^{i} \]
是不是想到了什么？
沒錯，我們可以把\(1\)到\(n\)的\(k\)次方求和，顯然這就是\(S_k(n)\)，展開式子就是
\[S_k(n) = \sum_{i=1}^{n}i^k = \sum_{i=1}^{n}\left({i^{\underline{k}}-\sum_{j=0}^{k-1}(-1)^{k-j}{ \left[\begin{matrix}k\\j\end{matrix}\right]}i^j}\right) \]
顯然的想法拆開求和符號，
對于第一項，轉化為組合數，
使用組合恒等式合并，再展開組合數，有：
\[\begin{aligned} &\sum\limits_{i=1}^{n}i^{\underline{k}}\\ =&k!\sum_{i=1}^{n}\dfrac{i^{\underline{k}}}{k!}\\ =&k!\sum_{i=1}^{n}{\left(\begin{matrix}i\\k\end{matrix}\right)}\\ =&k!{\left(\begin{matrix}n+1\\k+1\end{matrix}\right)}\\ =&\dfrac{(n+1)^{\underline{k+1}}}{k+1} \end{aligned}\]
對于第二項，只有 \(i^j\) 與 \(i\) 有關，交換求和符號，有：
\[\begin{aligned} &\sum_{j=0}^{k-1}(-1)^{k-j}{ \left[\begin{matrix}k\\j\end{matrix}\right]}\sum_{1}^{n}i^j \\= &\sum_{i=0}^{k-1} \cdot { \left[{\begin{matrix}k\\i\end{matrix}}\right]\,} \cdot S_i(n) \end{aligned}\]
這樣就得到了上面的式子，
擺脫了質數的限制，時間復雜度\(O(k^2)\)
伯努利數 伯努利多項式
？？？果斷抄式子走人
先求伯努利數，暴力算暴力算暴力算，多項式求逆
他們在說什么？不知道，走了
災難始終慢我一步
\(\dfrac{x}{e^x-1}=\sum\limits_{i=0}^{\infty}\dfrac{B_i}{i!}x^i\)
\(\sum\limits_{i=0}^\infty \dfrac{\large\beta_i(t)}{i!}\cdot x^i=\dfrac{x}{e^x-1}\cdot e^{tx}\)
\(S_k(n)=\dfrac{1}{k+1}\sum\limits_{i=0}^k\dbinom{k+1}{i}\cdot(n+1)^i\cdot B_{k+1-i}\)
斯特林數
挪出去了，見此處斯特林數
- 第一類斯特林數
- 第二類斯特林數
- 上升冪和下降冪
容斥原理
挪出去了，見此處容斥原理
- 容斥原理
- min-max容斥
寫在最后
\(\texttt{gyh}\)也太神了吧
為什么我這么菜/kk
哆啦誒喂夢，愛了愛了！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/6722.html
標籤：其他