[CF 528D] Fuzzy Search
首先考虑到只有四种字符。所以可以分四次来做。
对于每一种字符，我们定义 \(f(i)\) 为在 \(S\) 中的每 \(i\) 位置是否可以匹配。\(f(i)\) 就是如果相邻 \(k\) 个有当前字符就是 \(1\)，否则是 \(0\)。\(g(i)\) 就是 \(T\) 中这一位是否是当前字符。然后求的就是 \(\sum\limits_{x=0}^m \sum\limits_{i=0}^m f(i+x)g(i)\) 翻转过来就是卷积。
然后如果答案第 \(x\) 位为 \(T\) 中含有当前字符的个数，就说明 \(x\) 位在当前字符下可以。如果 \(x\) 在四种字符下都可以，那么 \(x\) 就是可以的。
P2791 幼儿园篮球题
吐槽：其实我挺烦这个梗的。我弟这两天总看各种 cxk 鬼畜，现在看着这个梗就反胃。
要求：\(\displaystyle \sum_{i=1}^k \dbinom{m}{i} \dbinom{n-m}{k-i} i^L\)
首先是经典斯特林数的式子。
\(\displaystyle m^n= \sum_{i=1}^m \begin{Bmatrix}n\\i\end{Bmatrix} \dbinom{m}{i} i!\)
代入到下面。
\(\displaystyle =\sum_{i=1}^k \dbinom{m}{i} \dbinom{n-m}{k-i}\sum_{j=1}^i \begin{Bmatrix}L\\j\end{Bmatrix}\dbinom{i}{j} j!\\ =\sum_{j=1}^k \begin{Bmatrix}L\\j\end{Bmatrix} j!\sum_{i=j}^k \dbinom{m}{i}\dbinom{n-m}{k-i}\dbinom{i}{j}\\=\sum_{j=1}^k \begin{Bmatrix}L\\j\end{Bmatrix} j! \dbinom{m}{j} \sum_{i=j}^k \dbinom{m-j}{i-j}\dbinom{n-m}{k-i}\\= \sum_{j=1}^k \begin{Bmatrix}L\\j\end{Bmatrix} j! \dbinom{m}{j} \sum_{i=0}^{k-j} \dbinom{m-j}{i} \dbinom{n-m}{k-i-j}\)
然后利用范德蒙德卷积：\(\displaystyle \sum \dbinom{n}{i} \dbinom{m}{k-i}=\dbinom{n+m}{k}\)
\(\displaystyle =\sum_{j=1}^k \begin{Bmatrix}L\\j\end{Bmatrix}j!\dbinom{m}{j}\dbinom{n-j}{k-j}\)
这就是答案。
以上内容都已经加入到计数题乱做那里
在学校就写这些
标签：begin,end,dbinom,sum,displaystyle,2023.1,Bmatrix,31,小记 From： https://www.cnblogs.com/cc0000/p/17080764.html