「from CommonAnts」一道数学题 题解

liu_cheng_ao 2017-04-24 23:08:45 2019-06-11 18:01:52

题面:

已知函数 f(k,x)(k,x\in \mathbb {N+}) 满足:

f(k,x)= \begin{cases} 1 & x=1\\ \sum_{i=1}^{x-1} f(k,i) + x^k & x>1 \end{cases}

现在给定 n,k ,求 f(k,n)

由于答案很大,你只需计算答案对 10^9+7 取模后的值。

数据范围

对于 20\% 的数据, n\leq 1000,k\leq 10

对于另外 10\% 的数据, n\leq 10^{18},k\leq 3

对于 40\% 的数据, n\leq 10^{18},k\leq 10

对于 50\% 的数据, n\leq 10^{1000000},k\leq 150

对于 80\% 的数据, n\leq 10^{1000000},k\leq 2000

对于 100\% 的数据, 1\leq n\leq 10^{1000000},1\leq k\leq 50000

题解

这题是用一个数据范围和 40\% 部分分一样的题加强数据范围得到的。

先来看看 40\% 做法:

经过推(zhao)式(gui)子(lv)我们可以得到一个递推式:

f(k,x)= \begin{cases} 1 & x=1\\ 2f(k,x-1) + x^k -(x-1)^k & x>1 \end{cases}

这个式子次数是一定的所以考虑矩阵乘法来算:

构造行向量

\mathbf {A_x}=\left( \begin{array}{ccccc} f(k,x) & x^k & x^{k-1} & ... & x^0 \end{array} \right)

构造转移矩阵:

\mathbf T=\left( \begin{array}{ccccc} 2 & 0 & 0 & 0 & 0\\ 0 &\binom k k & 0 & ... & 0 \\ \binom k {k-1} & \binom k {k-1} & \binom {k-1}{k-1} & ... & 0 \\ ... & & & & ...\\ \binom k 0 & \binom k 0 & \binom {k-1} 0 & ... & \binom 0 0\\ \end{array} \right)

\begin{cases} \mathbf {A_x}=\mathbf {A_{x-1}}\mathbf T\\ \mathbf {A_1}=\left( \begin{array}{ccccc} 1 & 1 & ... & 1 & 1 \end{array} \right) \end{cases}

答案就是 \mathbf {A_{n}}_{11},\mathbf {A_{n}}=\mathbf {A_1}\mathbf T^{n-1} ,使用矩阵幂即可在 O(k^3\log n) O(\log n +k^3 (\log p+\log k)) 时间复杂度内求得。

然而这个做法在 k 上的复杂度太高了,无法通过 k=2000 k=50000

不知道这个矩阵乘法能不能怎么优化一下?反正我不会。。

但是没有关系,我们还有别的做法:

首先观察递推式:

f(k,x)= \begin{cases} 1 & x=1\\ 2f(k,x-1) + x^k -(x-1)^k & x>1 \end{cases}

一个想法就是直接解这个递推式,但是因为有初值 f(k,1)=1 的限制 f 不可能是一个关于 x 的多项式。所以不能直接求。

但是没关系,我们可以把这部分提出来单独处理。具体说来就是:

构造一个关于 x 的多项式函数 g(k,x) ,使得:

f(k,x)+g(k,x)=2(f(k,x-1)+g(k,x-1))

其中 g(k,x)=2g(k,x-1)-x^k+(x-1)^k ,当 g(k,x) 是关于 x 的多项式时有一组惟一的 k-1 次多项式解。

这样,我们只要求出 g(k,1) g(k,n) 就能用快速幂算出 f(k,n)=2^{n-1}(1+g(k,1))-g(k,n)

现在我们的问题是求出 g(k,1) g(k,n)

一个基本的想法是直接算系数。设 g(k,x) 的第 i 项系数为 a_i 根据二项式展开,我们可以得到

2a_i=\binom k i +\sum_{j=i}^{k-1}\binom j i a_j ,i=0,1,2,...,k-1

移项,有

a_i=\binom k i +\sum_{j=i+1}^{k-1}\binom j i a_j ,i=0,1,2,...,k-1

直接求这个递推式我们就可以在 O(\log n +\log p+k^2) 的时间复杂度内解决问题辣!

不过这个 k^2 还不是很优美,有没有继续优化的方法呢?有。

考虑拉格朗日插值。只要我们能求出 g 在任何一点处的值,就能通过递推式 O(k\log k) 扩展 k 项并在 O(k) 时间内插值求出答案。

相对而言, g(k,0)=a_0 比较好求。

通过组(O)合(E)意(I)义(S)/推(zhao)式(gui)子(lv)我们发现

a_0=\sum _{i=1}^k \sum _{j=0}^{i-1} (-1)^j\binom i j (i-j)^k

提一个推出这个式子的思路:

观察递推式 a_i=\binom k i +\sum \limits_{j=i+1}^{k-1}\binom j i a_j ,i=0,1,2,...,k-1 可以发现, a_i 就相当于 k 个有标号元素中选取若干集合,考虑集合之间的排列顺序,剩余元素为 i 个时的方案总数。这样理解的话, \binom k i 相当于只选取一个集合的方案数, \sum \limits_{j=i+1}^{k-1}\binom j i a_j 相当于枚举了最后一个集合的大小。

这个问题比较经典,使用与和这个问题十分类似的伯努利数或第二类斯特林数很容易得到 a_0 的公式。(参见OEIS A000670)

那么问题变成了求 \sum \limits_{i=1}^k \sum \limits_{j=0}^i (-1)^j\binom i j (i-j)^k 。我们做如下推导:

\begin{eqnarray} a_0 &=&\sum _{i=1}^k \sum _{j=0}^{i-1} (-1)^j\binom i j (i-j)^k\\ &=&\sum _{d=1}^k \sum _{j=0}^{k-d} (-1)^j\binom {j+d} j d^k\\ &=&\sum _{d=1}^k d^k\sum _{j=0}^{k-d} (-1)^j\frac{(j+d)!}{j!d!}\\ &=&\sum _{d=1}^k \frac{d^k}{d!}\sum _{j=0}^{k-d} \frac{(-1)^j}{j!}(j+d)!\\ \end{eqnarray}

x_i=\frac{(-1)^i}{i!},y_i=(k-i)! ,容易发现后面的式子的每一项恰好是 x y 的卷积形式。

这样我们就可以愉快地FFT辣!

求出 g(k,0)=a_0 之后,只要用 g(k,x)=2g(k,x-1)-x^k+(x-1)^k 计算出 g(k,0) g(k,k-1) 就能用拉格朗日插值求出答案了。

FFT复杂度 O(k\log k) ,递推复杂度 O(k\log k) (要计算幂),插值复杂度 O(k) ,求幂的复杂度 O(\log p) ,读入和计算 n\mod p n\mod \varphi(p) 复杂度为 O(\log n)

总时间复杂度 O(\log n+\log p+k\log k)

这样这个问题就得到了解决。

UPD:我可能犯了个傻,这个题用和「bzoj4126」国王奇遇记加强版之再加强版 类似的方法可以做到 O(\log n+\log p+k) 的复杂度,并且不用做复杂的变换和FFT。

做法如下:

推出 g(k,x)=2g(k,x-1)-x^k+(x-1)^k 之后我们可以利用一个恒等式:

\sum \limits_{i=0}^{k}(-1)^i\binom{k}{i}g(k,i)=0

事实上这个式子对于任何 k-1 阶多项式都成立。

这样,我们可以用线性筛 O(k) 预处理 1^k,2^k,...,k^k 的值,然后利用递推式构造出一个关于 g(k,0) 的线性方程并 O(k) 将其求出。

利用刚才线性筛的结果我们还可以 O(k) 完成插值。这样我们就愉快地 O(\log n+\log p+k) 解决了这个问题。

可以参阅「bzoj4126」国王奇遇记加强版之再加强版 的题解,及杜教的课件《多项式及求和》。

这个方法对于任意的满足线性递推的多项式都适用。

我还是太菜了qwq。

共 7 条回复

liu_cheng_ao

感谢提醒递推式的笔误。至于您说的第一个问题,说是因为不符合 f(k,1)=1 的限制并没有问题,因为不考虑这个限制时原递推式是有解的。你的“平衡条件”等价于 f(k,1)=1 ,推出无解,恰恰说明了 f(k,1)=1 的限制是找不到递推式的关键约束。(而不是自己加限制之后用无解来解释无解,数学上的因果关系讨论要特别小心这一点。)

**不过这已经是我远古时期写的了,里面提到的很多问题都可以系统的解决,接受本文的观点对于有一定数学基础的读者有害无益。**这篇文章现在只能作为一架梯子,提供给需要它的人来攀登了。

hzoi2017_Ezio

还有一个地方,构造的矩阵的第二列下面的东西写反了。。。。从上到下应该是C(k,k)到C(k,1)吧。。。

hzoi2017_Ezio

在找到 f(k,x) 的递推式以后我们似乎可以直接解一下这个递推式。。。对于 f(k,1)=1 的限制是可以解决的。可以直接加判断条件来平衡,即

f(k,x)=2f(k,x-1)+x^k+(x-1)^k+[x=0](-1)^{k+1}

本菜鸡尝试了一下,未果。原因是无法找到关于 x^k 的生成函数的有效形式,也就无法推出数列的生成函数的封闭形式。 无法解递推式是因为好像是这个原因,而不是上面说的1的限制的原因。希望博主更正一下。

wxh010910

根本看不懂

liu_cheng_ao

啊 …… 我好菜啊 …… 这不就是随便 Stirling 一下就搞完了吗 …… 我果然好菜啊 ……

ceba_robot

膜拜LCA神犇,CTSC Au巨神

sosusosu

前排膜拜LCA神犇!OrzOrz