AIOJ

20 分做法

直接按照定义计算。

先预处理阶乘和逆阶乘。对于每个 $x = 0, 1, \ldots, n$ ，枚举 $i = 0, 1, \ldots, \min(k, x)$ ，用递推维护下降幂 $x^{\underline{i}}$ ，累加

\frac{x^{\underline{i}}}{x!\,(n-x)!}

即可。

时间复杂度 $O(nk)$ ，可以通过 $n$ 较小的数据。

当 $k = 0$ 时，

f(x)=\frac{1}{x!\,(n-x)!}.

因此

S(n)=\sum_{x=0}^{n}\frac{1}{x!\,(n-x)!} =\frac{1}{n!}\sum_{x=0}^{n}\binom{n}{x} =\frac{2^n}{n!}.

直接计算 $2^n \cdot (n!)^{-1} \bmod p$ 即可。

当 $k = 1$ 时，

f(x)=\frac{1+x}{x!\,(n-x)!}.

于是

S(n)=\sum_{x=0}^{n}\frac{1}{x!\,(n-x)!} +\sum_{x=0}^{n}\frac{x}{x!\,(n-x)!}.

第一部分为 $\dfrac{2^n}{n!}$ 。

第二部分中

\sum_{x=0}^{n}x\binom{n}{x}=n2^{n-1},

所以

\sum_{x=0}^{n}\frac{x}{x!\,(n-x)!} =\frac{n2^{n-1}}{n!} =\frac{2^{n-1}}{(n-1)!}.

答案为

\frac{2^n}{n!}+\frac{2^{n-1}}{(n-1)!}.

关键是把分母中的阶乘改写为组合数：

\frac{1}{x!\,(n-x)!}=\frac{1}{n!}\binom{n}{x}.

于是

S(n)=\frac{1}{n!}\sum_{i=0}^{k}\sum_{x=0}^{n}x^{\underline{i}}\binom{n}{x}.

当 $x<i$ 时，下降幂 $x^{\underline{i}}$ 中包含因子 $0$ ，对应项为 $0$ 。因此只需要考虑 $x\ge i$ 。

对于内层求和，有

x^{\underline{i}}\binom{n}{x} =\frac{x!}{(x-i)!}\cdot\frac{n!}{x!\,(n-x)!} =\frac{n!}{(x-i)!\,(n-x)!}.

令 $y=x-i$ ，则

\begin{aligned} \sum_{x=i}^{n}x^{\underline{i}}\binom{n}{x} &=\sum_{x=i}^{n}\frac{n!}{(x-i)!\,(n-x)!} \\ &=n^{\underline{i}}\sum_{y=0}^{n-i}\binom{n-i}{y} \\ &=n^{\underline{i}}\cdot 2^{n-i}. \end{aligned}

代回原式：

S(n)=\frac{1}{n!}\sum_{i=0}^{k}n^{\underline{i}}\cdot 2^{n-i}.

又因为

\frac{n^{\underline{i}}}{n!} =\frac{n!}{(n-i)!}\cdot\frac{1}{n!} =\frac{1}{(n-i)!},

所以

S(n)=\sum_{i=0}^{k}\frac{2^{n-i}}{(n-i)!}.

令 $j=n-i$ ，得到

S(n)=\sum_{j=n-k}^{n}\frac{2^j}{j!}.

这正是级数 $\sum \dfrac{2^j}{j!}$ 的一段连续子和。

实现时不需要保存所有阶乘。若 $p=2$ ，由 $n<p$ 可知只有 $n=0$ 或 $n=1$ ，直接计算即可。

下面考虑 $p$ 为奇质数的情况。先线性计算 $n! \bmod p$ ，再用费马小定理求出 $(n!)^{-1}$ ，得到最后一项

\frac{2^n}{n!}.

设

T_j=\frac{2^j}{j!}.

则

T_{j-1}=T_j\cdot\frac{j}{2}.

因此可以从 $j=n$ 倒着递推到 $j=n-k$ ，边递推边累加答案。

由于题目保证 $p$ 为质数且 $n<p$ ，所有 $1,2,\ldots,n$ 在模 $p$ 意义下都有逆元，阶乘也不为 $0$ 。

时间复杂度 $O(n+k)$ ，由于 $k\le n$ ，也就是 $O(n)$ 。空间复杂度 $O(1)$ 。