2020-2021:teams:legal_string:jxm2001:斯特林数
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:legal_string:jxm2001:斯特林数 [2020/08/22 18:00] jxm2001 |
2020-2021:teams:legal_string:jxm2001:斯特林数 [2020/08/22 21:24] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 436: | 行 436: | ||
| [[https://www.luogu.com.cn/problem/P5409|洛谷p5396]] | [[https://www.luogu.com.cn/problem/P5409|洛谷p5396]] | ||
| - | $$\begin{bmatrix}i\\ k\end{bmatrix}(0\le i\le n)$$ | + | $$\begin{Bmatrix}i\\ k\end{Bmatrix}(0\le i\le n)$$ |
| 考虑只有一个非空集合的方案的 $\text{EGF}$，有 $F(x)=\sum_{i=1}^{\infty} \cfrac {x^i}{i!}$。 | 考虑只有一个非空集合的方案的 $\text{EGF}$，有 $F(x)=\sum_{i=1}^{\infty} \cfrac {x^i}{i!}$。 | ||
| 行 571: | 行 571: | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
| + | |||
| + | ===== 练习题 ===== | ||
| + | |||
| + | ==== 习题一 ==== | ||
| + | |||
| + | [[https://www.luogu.com.cn/problem/P4091|洛谷p4091]] | ||
| + | |||
| + | === 题意 === | ||
| + | |||
| + | $$\sum_{i=0}^n\sum_{j=0}^i\begin{Bmatrix}i\\ j\end{Bmatrix}\times 2^j\times j!$$ | ||
| + | |||
| + | === 题解 === | ||
| + | |||
| + | 首先 $\begin{Bmatrix}i\\ j\end{Bmatrix}=0(j\gt i)$，于是 | ||
| + | |||
| + | $$\sum_{i=0}^n\sum_{j=0}^i\begin{Bmatrix}i\\ j\end{Bmatrix}\times 2^j\times j!=\sum_{i=0}^n\sum_{j=0}^n\begin{Bmatrix}i\\ j\end{Bmatrix}\times 2^j\times j!=\sum_{j=0}^n2^j\times j!\sum_{i=0}^n\begin{Bmatrix}i\\ j\end{Bmatrix}$$ | ||
| + | |||
| + | 直接展开第二类斯特林数，有 | ||
| + | |||
| + | $$\sum_{j=0}^n2^j\times j!\sum_{i=0}^n\begin{Bmatrix}i\\ j\end{Bmatrix}=\sum_{j=0}^n2^j\times j!\sum_{i=0}^n\sum_{k=0}^j \frac{(-1)^{j-k}}{(j-k)!}\frac{k^i}{k!}=\sum_{j=0}^n2^j\times j!\sum_{k=0}^j \frac{(-1)^{j-k}}{(j-k)!}\frac{k^{n+1}-1}{k!(k-1)}$$ | ||
| + | |||
| + | 需要注意 $k=0$ 时 $\cfrac{k^{n+1}-1}{k!(k-1)}=0$；$k=1$ 时 $\cfrac{k^{n+1}-1}{k!(k-1)}=n+1$。直接卷积即可，总时间复杂度 $O(n\log n)$。 | ||
2020-2021/teams/legal_string/jxm2001/斯特林数.1598090423.txt.gz · 最后更改: 2020/08/22 18:00 由 jxm2001
