发布时间 : 星期三 文章pascal中级教程第九章数学问题更新完毕开始阅读dc560f27af45b307e8719740
第九章 数学问题
9.1 多项式展开系数
源程序名 equal.???（pas, c, cpp） 可执行文件名 equal.exe 输入文件名 equal.in 输出文件名 equal.out 【问题描述】 二项式展开系数大家已经十分熟悉了：
?x?y?2iin?1??Cnxy i?0n现在我们将问题推广到任意t个实数的和的n次方(x1+x2+?+xt)n的展开式。我们想知
nnn道多项式(x1+x2+?+xt)n中的任意一项x11x22?xtt的系数。例如，将一个三项式(x1+x2+x3)3展开后，可以得到：
(x1+x2+x3)3=x1+x2+x3+3x1x2+3x1x3+3x1x2+3x1x3+3x2x3+3x2x3+6x1x2x3 其中，
333222222x12x2的系数为3
【输入】
第一行，两个整数n和t，中间用空格分隔。分别表示多项式幂和项数。 第二行，t个整数n1, n2, ?， nt，中间用空格分隔。分别表示x1, x2, ?, xn的幂。（n1+n2+?+nt=n，1≤n, t≤12） 【输出】 仅一行，一个整数（保证在长整型范围内）。表示多项式(x1+x2+?+xt)n中的项
n2x1n1x2?xtnt的系数。
【样例】 equal.in 3 3 2 1 0
【知识准备】 组合数运算； 【算法分析】
equal.out 3
二项式展开； 代数式的恒等变形。
n（1）利用二项式展开公式(x?y)?n?Ci?0inxiyn?i推广到多项式
(x1?x2????xt)n的展开：
k1k1(x1?x2????xt)??Cnx1(x2?x3????xt)n?k1nk1?0nn?k1nk2k2n?k1?k2??Cx??Cn?k1x2(x3?x4????xt)k1k1n1k1?0k2?0?????Cx??Ck1k1n1k1?0k2?0nn?k1k2k2n?k12x???n?k1?k2???kt?2kt?1n?k1?k2???kt?2kt?1?0?C?xkt?1t?1ktkt??Cn?k1?k2???kt?1?xtkt?0nt
其中含有x11x22??xtt(n1?n2???nt?n)的一项即为上式右边展开后的一项：
nt?1nt?1ntntn1n1n2n2Cnx1?Cn?n1x2???Cn?n1?n2???nt?2xt?1?Cntxt
t?1tt?1t212整理得到：Cn1?Cn?n1???Cn?n1?n2???nt?2?Cnt?x1x2?xt?1xt
nnnnnnnnnnn ①
所以要想求(x1+x2+?+xt)n 的任意一项x11x22?xtt的系数只要将①式中令x1=x2=?
nnnnnnnt?1t2=xt=1，得到Cn1?Cn?n1???Cn?n1?n2???nt?2?Cnt
（2）因为
n1Cn?n!
n1!(n?n1)!(n?n1)!
n2!(n?n1?n2)!
n2Cn?n1???
nt?1Cn?n1?n2???nt?2?(n?n1?n2???nt?2)!(n?n1?n2???nt?2)!?
nt?1!(n?n1?n2???nt?2?nt?1)!nt?1!nt!
ntCn?tnt! nt!nnnn
t?1t2所以Cn1?Cn?n1???Cn?n1?n2???nt?2?Cnt?n!
n1!n2!?nt?1!nt!
（3）由分析（1）、（2）求x11x22?xtt的系数化为求上述的除法运算： ① 先计算n!； ② 将n!逐一去除n1, n2, ?, nt； ③ 最后的商为所求结果。
由于题目所给n≤12，计算n!可在长整型范围内，无需采用高精度运算。 设数组no:array[1..t]为nt；total为n!。主要算法描述如下
nnn total:=1;
for i:=1 to n do total:=total+i; {求n!} for i:=1 to t do
for j:=1 to no[i] do total:=total div j; {整除n!}
9.2 两数之和
源程序名 pair.???（pas, c, cpp） 可执行文件名 pair.exe 输入文件名 pair.in 输出文件名 pair.out 【问题描述】 我们知道从n个非负整数中任取两个相加共有n*(n-1)/2个和，现在已知这n*(n-1)/2个和值，要求n个非负整数。 【输入】 输入文件仅有一行，包含n*(n-1)/2+1个空格隔开的非负整数，其中第一个数表示n(2 本题的规模只有10，看似一道搜索题。其实不然，搜索固然有可能出解，但是本题是有多项式级算法的。本题的难点就在于要理清这看似混乱的n(n-1)/2个“和”的关系，从中寻找突破口。 那么，突破口在哪里呢?n(n-1)/2个“和”是任意给出的，并未按照什么指定的顺序，所以从表面上看这些数（和）之间似乎没有什么区别。当然，我们必须在这些数（和）中制造出一些区别来，因为没有区别我们也就无从下手。对什么信息也没有的一些数，惟一可以制造出的区别就是它们之间的大小关系。根据数的大小关系，我们可以对这n(n-1)/2个数排序。排完序后，可以成为突破口的无非就是那么几个，最小的数（和）、最大的数（和）、中位数??我们不可能随便找一个数出来作为突破口，因为随便找一个数的话，大小关系就失去意义了。所以，这时我们需要注意的只有这么几个数了：最小的数（和）、最大的数（和）和中位数。 中位数看上去似乎也很难成为突破口，因为我们无法预知中位数是哪两个数的和。而最小、最大的两个数(“最小的和”与“最大的和”)则不同，最小的和必然是最小的两个数之和，最大的和必然是最大的两个数之和。由问题对称性，最小与最大其实是等价的，所以我们可以只考虑最小的情况，解决了最小，最大也就相应解决了。 最小的和是最小的两个数之和，这是一条已经确定的与最小的两个数相关的信息。当然，就凭这些信息，我们还是无法知道最小的两个数究竟是多少，这是我们目前面临的一个障碍。我们不妨先跳过这个障碍，考虑以后的问题。我们可以假设已经知道最小的数的大小，这样 我们又可以很顺利的知道次小的数是多少了（最小的和-最小的数）。 知道最小的两个数的大小对我们有什么好处呢？其实关键是知道最小的数是多少，这是至关重要的，因为很多特殊的和都与最小的数有关。试想，我们知道了最小的两个数，也就确定了一个和（最小的和）。把这个“和”从n(n-1)/2个和中去掉，剩下的n(n-1)/2-1个和中又会产生新的最小的和。这个新的最小的和是哪两个数的和呢?应该是最小的数与第三小的数的和。由于我们假设已经知道最小的数，我们自然就可以通过作差得到第三小的数了。 得到前三小的数后，我们就确定了3个“和”了。籽这三个“和”从n(n-1)/2个和中去掉，剩下的n(n-1)/2-3个和中又会产生新的最小的和。这个新的最小的和必然是最小的数与第四小的数的和。由于最小的数已知，第四小的数就可以算出了。 更一般的情况，知道了前k小的数，那么我们就确定了k(k-1)/2个和了。将这k(k-1)/2个和从n(n-1)/2个和中去掉，剩下的n(n-1)/2-k(k-1)/2个和中又会产生新的最小的和。这个新的最小的和必然是最小的数与第k+1小的数的和。由于最小的数已知，第k+1小的数就可以通过作差得到。 如此，在知道了最小的数的情况下，不断的从当前最小的和入手，就可以从小到大依次把所有的数都推算出来了。 不过，有一点还是需要注意的，前面所有的推导都是建立在最小的数已知的情况下的，但实际情况是最小的数未知。所以，我们还需要创造条件，使最小的数由未知变为已知。 一个简单而可行的方法就是枚举最小的数。简单就不必说了，为什么说枚举是可行的呢?因为题目规定所有的数都不超过100000，因此总共需要枚举的方案数最多只有100000。而在知道最小的数的情况下，推算出其他数的代价是O(n2)，n≤10。100000*102的计算代价是可以承受的。 最后，我们总结一下前面得到的算法。 （1）枚举最小的数； （2）根据最小的数和最小的和，得到次小的数； （3）由前k小的数推出第k+1小的数。 算法的时间复杂度是O(Cn2)，其中C表示数值的大小。 从本题的解题过程中，我们看到其中最关键的一步就是以最小的和作为突破口。在解决数学问题的时候，很多情况下从为数不多的信息中寻找突破口是至关重要的。找到了突破口，问题本身也就迎刃而解了。