数学题选做以及数学知识学习笔记（持续更新ing）
由于只是杂碎的学一学，就按照题目来进行整理了
目录
P6620 [省选联考 2020 A 卷] 组合数问题
计算
\[\left(\sum_{k=0}^{n}f(k)\times x^k\times \binom{n}{k}\right)\bmod p
\]
的值。
这个地方要引入一个东西叫做下降幂，因为我们发现这个多项式摆在这里很奇怪/yun，我们把它展开：
\[f(x)=\sum_{i=0}^{m}a_ix^i
\]
把这个东西转化成一个下降幂多项式
\[f(x)=\sum_{i=0}^{m}a_ix^i=\sum_{i=0}^{m}b_ix^{\underline{i}}
\]
然后我们知道下降幂跟组合数有一个比较好的结合方式即：
\[\binom{n}{k}\times k^{\underline{m}}=\frac{n!}{k!(n-k)!}\times \frac{k!}{(k-m)!}=\frac{n!}{(n-k)!(k-m)!}=\frac{n!}{(n-m)!}\times\frac{(n-m)!}{(n-k)!(k-m)}=\binom{n-m}{k-m}\times n^{\underline{m}}
\]
那我们把式子结合一下就是：
\[\sum_{k=0}^{n}\sum_{i=0}^{m}b_ik^{\underline{i}}\times x^k \times \binom{n}{k}
\\
=\sum_{k=0}^{n}\sum_{i=0}^{m}b_in^{\underline{i}}\times x^k \times \binom{n-i}{k-i}
\\
=\sum_{i=0}^{m}b_in^{\underline{i}}\sum_{k=0}^{n}x^k\times\binom{n-i}{k-i}
\]
然后改为枚举\(k-i\)
\[=\sum_{i=0}^{m}b_in^{\underline{i}}\sum_{k=0}^{n-i}x^{k+i}\times\binom{n-i}{k}
\\
=\sum_{i=0}^{m}b_in^{\underline{i}}x^i\sum_{k=0}^{n-i}x^k\times\binom{n-i}{k}
\\
=\sum_{i=0}^{m}b_in^{\underline{i}}x^i(x+1)^{n-i}
\]
但是我们只知道\(a\)不知道\(b\)啊，所以这里还要把下降幂多项式转回去
\[x^n=\sum_{i=0}^{n} {n \brace i}x^{\underline{i}}
\]
带入一下就是
\[\sum_{i=0}^{m}a_ix^i
\\
=\sum_{i=0}^{m}a_i\sum_{k=0}^{i}{i \brace k}x^{\underline{k}}
\\
=\sum_{k=0}^{m}x^{\underline{k}}\sum_{i=k}^{m}{i \brace k}a_i
\\
=\sum_{k=0}^{m}b_kx^{\underline{k}}
\]
即
\[b_k=\sum_{i=k}^{m}{i \brace k}a_i
\]
然后把斯特林数处理出来就可以做啦
#269. 【清华集训2016】如何优雅地求和
给定函数\(f\)，\(n\)和\(x\)，要你求出来一个变换\(Q\)的值\(mod 998244353\)的结果，变换的形式如下：
\[Q(f,n,x)=\sum_{k=0}^{n}f(k)\binom{n}{k}x^k(1-x)^{n-k}
\]
感觉跟上一题一样熟悉呀！
还是亲切的组合数，亲切的多项式函数，唯一不同的大概就是后面的\(x\)的部分，那我们直接跳到这一步：
\[\sum_{k=0}^{n}\sum_{i=0}^{m}b_ik^{\underline{i}}\times x^k \times (1-x)^{n-k}\times\binom{n}{k}
\\
=\sum_{k=0}^{n}\sum_{i=0}^{m}b_in^{\underline{i}}\times x^k\times (1-x)^{n-k}\binom{n-i}{k-i}
\\
=\sum_{i=0}^{m}b_in^{\underline{i}}\sum_{k=0}^{n}x^k(1-x)^{n-k}\binom{n-i}{k-i}
\\
=\sum_{i=0}^{m}b_in^{\underline{i}}\sum_{k=0}^{n-i}x^{i+k}(1-x)^{n-i-k}\binom{n-i}{k}
\\
=\sum_{i=0}^{m}b_in^{\underline{i}}(x+1-x)^{n}
\\
=\sum_{i=0}^{m}b_in^{\underline{i}}
\]
CF932E Team Work
给定 $ n,k $，求：
\[\sum_{i=1}^n\binom n i \times i^k
\]
$ 1 \leq k \leq 5000,1 \leq n \leq 10^9 $
原汁原味
\[\sum_{i=1}^n\binom n i \times i^k
\\
=\sum_{i=1}^n\binom{n}{i}\sum_{j=0}^k {k \brace j}i^{\underline{j}}
\\
=\sum_{i=1}^n\sum_{j=0}^k {k \brace j}i^{\underline{j}}\binom{n}{i}
\\
=\sum_{i=1}^n\sum_{j=0}^k {k \brace j}\binom{n-j}{i-j}n^{\underline{j}}
\\
=\sum_{j=0}^{k}{k \brace j}n^{\underline{j}}\sum_{i}^{n}\binom{n-j}{i-j}
\\
=\sum_{j=0}^{k}{k \brace j}n^{\underline{j}}\sum_{i=0}^{n-j}\binom{n-j}{i}\
\\
=\sum_{j=0}^{k}{k \brace j}n^{\underline{j}}2^{n-j}
\]
CF1278F Cards
有 \(m\) 张牌，其中一张是王牌。现在你执行 \(n\) 次如下操作：洗牌后查看第一张牌是什么。
令 \(x\) 为洗牌后第一张牌为王牌的次数，现在假设洗牌时 \(m!\) 种牌的排列出现的概率均相等，求 \(x^k\) 的期望值。
式子挺显而易见的：
\[E(x^k)=\sum_{i=0}^{n}i^k\binom{n}{i}(\frac{1}{m})^i(\frac{m-1}{m})^{n-i}
\\
=\sum_{i=0}^{n}\sum_{j=0}^{k}{k \brace j}i^{\underline{j}}\binom{n}{i}(\frac{1}{m})^i(\frac{m-1}{m})^{n-i}
\\
=\sum_{i=0}^{n}\sum_{j=0}^{k}{k \brace j}\binom{n-j}{i-j}n^{\underline{j}}(\frac{1}{m})^i(\frac{m-1}{m})^{n-i}
\\
=\sum_{j=0}^{k}{k \brace j}n^{\underline{j}}\sum_{i=0}^{n}\binom{n-j}{i-j}(\frac{1}{m})^i(\frac{m-1}{m})^{n-i}
\\
=\sum_{j=0}^{k}{k \brace j}n^{\underline{j}}\sum_{i=0}^{n-j}\binom{n-j}{i}(\frac{1}{m})^{i+j}(\frac{m-1}{m})^{n-i-j}
\\
=\sum_{j=0}^{k}{k \brace j}n^{\underline{j}}(\frac{1}{m})^j\sum_{i=0}^{n-j}\binom{n-j}{i}(\frac{1}{m})^{i}(\frac{m-1}{m})^{n-i-j}
\\
=\sum_{j=0}^{k}{k \brace j}n^{\underline{j}}(\frac{1}{m})^j\sum_{i=0}^{n-j}\binom{n-j}{i}(\frac{1}{m})^{i}(\frac{m-1}{m})^{n-i-j}
\\
=\sum_{j=0}^{k}{k \brace j}n^{\underline{j}}(\frac{1}{m})^j1^{n-j}
\\
=\sum_{j=0}^{k}{k \brace j}n^{\underline{j}}(\frac{1}{m})^j
\]