tokitsukaze ans unlimited array.md

题解

######By yijan 感谢zbww大佬大力支持

Step one

原多项式是$ F(x) $ 最终要求的是差分$ n+1 $次后数组的和。

因为差分$ n+1 $次得到的前无穷项的和,就是差分$ n $次后的第无穷项。

定义多项式$ F(x) ​$的差分操作。一个多项式差分后还是一个多项式。具体而言,$ F(x) ​$差分后是$\Delta F(x)​$,那么$\Delta F(x) = F(x) - F(x-1)​$

当然,这个差分和题目里面的不一样。题目中差分后第一项还是第一项。这个的确会造成影响。但是,对于第$ n $次差分这只影响前$ n-1 $项。当我们求出了进行$n$阶差分后的函数$f(x)$后,只需要求出$ f(\infin) $

也就是说,到此为止我们已经成功把问题转化成了多项式的差分

Step two

接着说明一下一个$ n $次多项式$F(x)$,差分$ n $次后一定是一个常量函数。这虽然看起来非常显然,但实际上还是要写一下的。为方便理解不用sigma了。。

$ F(x) = a_0x^0 + a_1x^1 + a_2x^2 +…+a_nx^n $

给它差分一下

$ \Delta F(x) = a_1 + a_2[x^2-(x-1)^2]+…+a_n[x^n-(x-1)^n] $

这里的关键在于,$ x^n-(x-1)^n $ 算出来一定是一个$n-1$次多项式。(二项式定理展开就显然了(实际上本来就很显然))

也就是说,一个$ n $次多项式每进行一次差分就会变成$n-1$次多项式。因此,原题的$n$次多项式进行操作后一定会变成一个常量函数

这里也证明了一点,求$ f(\infin ) $等价于求$ f(n) $(因为从$n$开始后面全是常量。

到这里总结一下,也就是说,虽然从原题看起来差分$n$次后是一个找不到规律的奇怪的式子,但是它从第$n$项起的常量就等于对原多项式进行$n$次差分后的常函数。我们现在的目标变成了求题目给出的函数差分$n$次后的结果。

Step Three

怎么求函数差分$ n $次后的结果呢?

首先,根据数列差分的定义,我们知道如果 $ F(x) = f_1(x) + f_2(x)$ 那么显然$\Delta F(x) = \Delta f_1(x) + \Delta f_2(x)$ 也就是说,$n$次多项式函数的差分可以分成$n$个单项式作为函数求差分的和。 这$ n $个单项式的次数是从$0$到$n$的。也就是说,其中有$n-1$个都会变成0。(把一个低于n次的多项式差分n次显然会变成0)

也就是说,比如

$ F(x) = a_0x^0 + a_1x^1 + a_2x^2 +…+a_nx^n $

则 $\Delta F(x) = \Delta f(x) $其中$f(x) = a_0x^n$

把系数$a_0$提出去,下面就是求$x^n$的$ n $阶差分。

Step Four

非常显然,对$x^n$求$n$阶差分等价于对$x^n$求一次差分后再进行$n-1$次差分。

先尝试进行一次差分

$\Delta (x^n) = x^n - (x-1)^{n} $

因此 二项式定理展开一下,推出

$\Delta (x^n)= - \sum_{k=0}^{n-1} \bigl( \begin{smallmatrix} n \k \end{smallmatrix} \bigr)(-1)^{n-k}x^k$

然后又变成了$n-1$次。对$n-1$次求差分又只需要最高位。也就是,这里需要保留的系数是

$(\begin{smallmatrix} n \n-1 \end{smallmatrix} \bigr) = n$

最后把所有的系数提出来,就是$n!$然后乘上最前面的常数$a_n$

因此 答案 $a_n n!$

Step Five

实现

n 1e9

我还真只会打表