P6031 CF1278F Cards 加强版是哪款游戏卡牌？

\(\text{Solution}\) 推式子 有答案为 \[\begin{aligned} Ans &=\sum_{i=0}^n i^k\dbinom n i (\frac 1 m)^i (1-\frac 1 m)^{n-i} \end{aligned} \] \(i\) 的上限为 \(n\)，交换求和顺序不好优化，看到 \(i^k\)，试试第二类斯特林数 \[\sum_{i=0}^n i^k\dbinom n i (\frac 1 m)^i (1-\frac 1 m)^{n-i} = \sum_{i=0}^n \dbinom n i (\frac 1 m)^i (1-\frac 1 m)^{n-i} \sum_{j=0}^k \begin{Bmatrix}k\\j \end{Bmatrix}j! \dbinom i j \] 第二个求和符号后面只有 \(\dbinom i j\) 受 \(i\) 限制，而前面有 \(\dbinom n i\)，考虑恒等式（组合意义即可） \[\dbinom n i \dbinom i j = \dbinom n j \dbinom{n-j}{i-j} =\dbinom n j \dbinom{n-j}{n-i} \] 代回原式即可把后一部分提前 \[\begin{aligned} \sum_{i=0}^n \dbinom n i (\frac 1 m)^i (1-\frac 1 m)^{n-i} \sum_{j=0}^k \begin{Bmatrix}k\\j \end{Bmatrix}j! \dbinom i j &= \sum_{j=0}^k \begin{Bmatrix}k\\j \end{Bmatrix}j! \dbinom n j\sum_{i=j}^n \dbinom{n-j}{i-j} (\frac 1 m)^i (1-\frac 1 m)^{n-i} \\ &= \sum_{j=0}^k \begin{Bmatrix}k\\j \end{Bmatrix}j! \dbinom n j\sum_{i=0}^{n-j} \dbinom{n-j}i (\frac 1 m)^{i+j} (1-\frac 1 m)^{n-j-i} \\ &= \sum_{j=0}^k \begin{Bmatrix}k\\j \end{Bmatrix}j! \dbinom n j m^{-j} \end{aligned} \] 第二行把 \((i-j) \rightarrow i\)，然后二项式定理合并了第二个求和式子 此时已经有了 \(O(k\log k)\) 的做法了，多项式卷积直接弄出 \(S_k\) 不过可以更优，上式瓶颈在 \(S_k\) 中，考虑用容斥把 \(S_k\) 拆开 \[\begin{Bmatrix}k\\j \end{Bmatrix}=\frac1{j!}\sum_{i=0}^j {(-1)}^j\dbinom j i (j-i)^k \] 那么 \[\begin{aligned} \sum_{j=0}^k \begin{Bmatrix}k\\j \end{Bmatrix}j! \dbinom n j m^{-j} &= \sum_{j=0}^k \dbinom n j m^{-j} \sum_{i=0}^j {(-1)}^j\dbinom j i (j-i)^k \\ &= \sum_{j=0}^k \dbinom n j m^{-j} \sum_{i=0}^j {(-1)}^{j-i}\dbinom j i i^k \\ &= \sum_{i=0}^k i^k (-1)^i \dbinom n i \sum_{j=i}^k \dbinom{n-i}{n-j} ({\frac 1 m})^j (-1)^j \end{aligned} \] 第二行同样是把 \((j-i)\rightarrow i\)，然后出现的 \(\dbinom n j \dbinom j i\) 同样处理，并提前枚举 \(i\) 前一个求和可以线筛预处理 \(i^k\) 考虑后面的求和式子，记为 \(f(i)\)，找到一种递推关系 \(O(k)\) 预处理 处理手段是把组合数按帕斯卡公式展开 那么 \[\begin{aligned} f(i)=\sum_{j=i}^k \dbinom{n-i}{n-j} ({\frac 1 m})^j (-1)^j &= f(i+1)+\sum_{j=i}^k \dbinom{n-i-1}{n-j-1} ({\frac 1 m})^j (-1)^j \\ &=