论省选中有意思的一道组合题

Posted on Views:

省选结束了，本人作为划水3年的OIer宣告原地退役，唯一写出正解的是D1T2。我其实觉得这道题挺有意思的（虽然大佬们都说只是推式子而已……嘛，毕竟本来没期待自己能做出来），就写篇文章记一下自己的想法吧。

题意

给定整数n, x, P\le 10^9，以及一个m \le 1000次整系数多项式f，求

\left[\sum_{k=0}^nf(k)x^k\binom{n}{k}\right]\bmod P

心路历程

先乱搞一波

看到这个题目的第一眼我觉得颇为眼熟。虽然没学过奥数，印象当中《具体数学》里面花了很大笔墨讲由这种指数，多项式以及二项式系数组合而成的和式的处理方法，似乎最后也讲到了机械求和法，然并卵，印象止步于印象，机械求合法太复杂了自己并没有记下来。

但是自己的残存记忆告诉我机械求和法的第一步是把求和式化成超几何函数，虽然后者我更没办法但是本着有逼就要装的思想……为什么不试一试呢？

什么样的级数是超几何的？《具体数学》里面给出的方法是求相邻项之比幸好这个我还没有忘记，而显而易见地是多项式求比是求不出具有良好形式的结果的，因此多项式必须转化为性质更优良的下降阶乘幂处理（关于下降阶乘幂我记得两年之前就写过一篇成套方法和有限微积分的博文，现在想来下降阶乘幂在离散求和问题当中真的有非常良好的性质，我在这里就沿用《具体数学》里的记号了：k^{\underline m} = \prod_{i=0}^m (k-i)）：

\begin{aligned} \frac{(k+1)^{\underline{m}}x^{k+1}\binom{n}{k+1}}{k^{\underline{m}}x^k\binom{n}{k}} &= \frac{(k+1)x(n-k)}{(k-m+1)(k+1)} \\ &= \frac{(n-k)x}{k-m+1} \end{aligned}
不出所料，结果是一个有理函数，也就是说可以化成高斯超几何函数呢！

不出所料，半瓶水的某人也就知道这些了（悲）。

但是下降阶乘幂的思想是可以有的嘛！

部分分摸鱼

在乱搞如预想的那般失败之后我就开始看部分分。

部分分里面有一个f是常数的，愣了一会发现能用二项式定理，答案是(1+x)^n。

然后还有一个x=1的。这个要怎么解决？

从最简单的一次多项式开始：

\sum_{k=0}^nk\binom{n}{k}=?
推式子本人是不会的，结论也忘了，但是从组合意义上还是好想的：k\binom{n}{k}就是从n个人里面选k个人，然后钦定一个做队长的方案数，把它求和，就是从n个人里面选若干人，然后从当中钦定一个队长的方案数。这是先选人再定队长的顺序，我们可以先选队长再选人嘛！从n个人里面选一个队长有n种方法，剩下的(n-1)个人要不要都行，所以是2^{n-1}种，二者相乘：
\sum_{k=0}^nk\binom{n}{k}=n2^{n-1}
就把一次的式子推出来了。

那二次的式子呢？

\sum_{k=0}^nk^2\binom{n}{k}=?
如果沿用之前运用组合意义化简的思路，那k^2就有“可以重复选”的含义在，是不好处理的。但是之前的乱搞告诉我们，是不是化成下降阶乘幂会好处理一点呢？
\sum_{k=0}^nk(k-1)\binom{n}{k}=?
答案是肯定的，思路和一次的完全一样，只是从“选队长”变成了“选队长和副队长“，因此很快就可以得出：
\sum_{k=0}^nk(k-1)\binom{n}{k}=n(n-1)2^{n-2}
然后就可以很快地推广出去了：
\sum_{k=0}^nk^{\underline{m}}\binom{n}{k}=n^{\underline{m}}2^{n-m}
这样几个部分分就基本拿到了。

把两者组合起来

那如果x\neq 1且f非常数要怎么做呢？我们不妨还是把f想成下降阶乘幂（怎么拆另说）：

\sum_{k=0}^nk^{\underline{m}}x^k\binom{n}{k}=?
然后思考其组合意义，稍开脑洞即可得到：

k^{\underline{m}}x^k\binom{n}{k}是从n个人里面挑选k个人，再给让当中m人担任m个不同职位，最后再让每个人从x种颜色的帽子当中选一个戴上的方案数（不要问我怎么想到戴帽子的）。

因此，由加法原理，对其求和之后就是从n个人里面挑选若干个人，再给让当中m人担任m个不同职位，最后再让每个人从x种颜色的帽子当中选一个戴上的方案数。

那我们故技重施，调换顺序，不妨先从n个人当中调出担任m个职位的那m个人（n^{\underline{m}}种取法），再先让他们先选帽子（x^m种选法），然后让剩下的(n-m)个人要不挑一个颜色的帽子进队要么滚蛋（(1+x)^{n-m}种取法）。于是就有了：

\sum_{k=0}^nk^{\underline{m}}x^k\binom{n}{k}=n^{\underline{m}}x^m(1+x)^{n-m}
哇，式子就推出来了！

多项式拆分

现在基于下降阶乘幂的式子已经推出来了，唯一剩下的就是把给定的f拆成若干个下降阶乘幂的线性组合。

\sum_{i=0}^ma_ik^i = \sum_{j=0}^m b_jk^{\underline{j}}
即求b_j的过程。

显而易见地，我们需要从高次到低次拆，这样后拆出来的幂才不会对之前的结果造成影响。

同时显然的是，我们需要知道下降阶乘幂展开后对应多项式的系数。

现在回过来看，朴素的多项式乘法是完全可以胜任的。但是写多项式乘法毕竟比较繁琐，不如观察多项式系数的规律。

令c[m, n]表示下降阶乘幂x^{\underline m}的展开式当中x^n的系数。则由下降阶乘幂的定义：

x^{\underline m} = x^{\underline{m-1}}[x-(m-1)],\quad (m\ge 1)
可以得出递推式：
c[m,n]=c[m-1,n-1]-(m-1)c[m-1,n]
边界条件是c[0,0] = 1以及c[m,0]=0\quad \forall m>0。这是一个类似杨辉三角的递推式，自然可以在\mathcal{O}\left(m^2\right)的时间内算出来，代码也好写。

至此，这道题目就完全解决了。

其实不止如此，这个三角在考场上让我感到非常眼熟，回去查证了一下，果然c[m,n]就是所谓的带符号的第一类斯特林数，“下降阶乘幂的展开系数”正是其重要的性质之一。

感想

这道题对我的感触是比较深刻的，尤其是做出来之后，颇有一种成就感。

细想来，我组合数学的公式其实几乎都没有背过，故而几乎所有的式子都是现场推出来的。而且推理的方式也不纯代数的暴算，而是通过combinatorial proof的方式。自从PACT学来这招之后我觉得这种方法实在是精妙。在最后自己还稀里糊涂地推演出了斯特林数的递推公式，或许这种高大上的组合数本身离我们就不遥远吧。

而话又说回来，大佬们看我写的这篇文章，只怕有些不耐烦与乏味吧。那些认真学习过组合数学的选手，大概看到这道题只剩下满满的套路，毕竟斯特林数名声在外，falling factorial这个套路熟悉了也不难想到，而类似的组合式子大概课后的习题会有很多吧。看到诸多大佬将D1T2云淡风轻地说成“裸的推式子”，他们做这道题时的从容大概可见一斑。只有像自己这样偶尔翻翻《组合数学》和《具体数学》，半瓶水晃荡的，才会在考场上各种心情复杂，一惊一乍了。

然而换一个角度，我觉得这道题对我来说真的不错，自己之前偶尔翻翻书也是。作为一道数学题，这道题并没有远远超出我的见识让我一筹莫展，也没有远远低于我的见识让我秒杀，恰是我稍微努力一下就能解决的。而这次考试正是给了日渐颓废，游手好闲的我一个“努力一下”的契机。就结果来看，解决这道题不仅给了我市选的信心，也给了我组合数学的信心，还让我在结题过程中观赏到了极佳的风景，似乎确实不赖。尤其是后者，若放在平时做题，随时可以查找资料，正确答案触手可及，那结论得出时大概也不会有考场上那么惊喜，那么愉悦了。

逆 转

啊？出分了？！

我考个250都能压线进队？！

我可是根本就没认真复习啊，半年没碰OI了……

唉，看来这次强行退役失败了，心情复杂……