重要定理和公式   一、常见递推关系 1.Fibonacci 数列 A(1)=1; A(2)=1; A(n)=A(n-1) + A(n-2); 2.Catalan数： 考虑具有n个结点不同形态的二叉树的个数 H(n) H (0) = 1; H (n) = H (0) H (n-1) + H (1) H (n-2) + H (2) H (n-3) … + H (n-2) H (1) + H (n-1) H (0) ; -> H (n) = (1/ (n+1)) * C (n, 2n) 3. 第二类Stirling数： s(n,k)表示含n个元素的集合划分为k个集合的情况数 A.分类：集合{An}存在，则有s(n-1,k-1); 不存在则An和放入k个集合中的任意一个， 共k*s(n-1,k)种。 0 (k=0 or n<k) s(n,k)={ s(n-1,k-1)+k*s(n-1,k) (n>k>=1) *:求一个集合总的划分数即为 sigema(k=1..n) s(n,k) . 4．数字划分模型 *NOIP2001数的划分 将整数n分成k份，且每份不能为空，任意两种分法不能相同(不考虑顺序)。 d[0,0]:=1; for p:=1 to n do for i:=p to n do for j:=k downto 1 do inc(d[i,j],d[i-p,j-1]); writeln(d[n,k]); *变形1：考虑顺序 d[ i, j] : = d [ i-k, j-1] (k=1..i) *变形2：若分解出来的每个数均有一个上限m d[ i, j] : = d [ i-k, j-1] (k=1..m) 5．错位排列   d[1] = 0; d[2] = 1; d[n] = (n-1) * (d[n-1] + d[n-2]) 6. 二、图论与计算几何 1．度边定理： sigema di = 2*E 2．.三角形面积 |x1 y1 1| s=|x2 y2 1|=x1y2+x2y3+x3y1-x3y2-x2y1-x1y3 |x3 y3 1| *海伦公式： 令p=(a+b+c)/2, 则 S=sqrt(p*(p-a)*(p-b)*(p-c)); 三、组合公式 1．长度为n的0-1串中最多含k个1的 例 长度为N (N<=31)的01串中1的个数小于等于L的串组成的集合中找出按大小排序 后的第I个01串。 2给定序列入栈出栈后可形成的情况总数为 C(n,2n) – C(n-1,2n)+1. 例fjoi2000 在一个列车调度站中，2条轨道连接到2条侧轨处，形成2个铁路转轨站，如下图所 示。其中左边轨道为车皮入口，右边轨道为出口。编号为1，2，……，n的N个车皮从入 口依次进入转轨站，由调度室安排车皮进出栈次序，并对车皮按其出栈次序重新编序 a1,a2,……,an。 给定正整数N（1<=n<=300），编程计算右边轨道最多可以得到多少个不同的车皮编序方案。 例如当n=3时，最多得到6组不同的编序方案。 四、数论公式 1．模取幂 a^b mod n= (..(a mod b)*a) mod b)*a..) mod b; 2．n的约数的个数 若n满足n=a1^n1 * a2^n2 * a3^n3 * ... * am^nm,则n约数的个数为 (n1+1)(n2+1)(n3+1)...(nm+1) 3． 五、代数   1带权中位数 我国蒙古大草原上有N（N是不大于100的自然数）个牧民定居点P1（X1，Y1）、P2（X2，Y2）、 …Pn（Xn，Yn），相应地有关权重为Wi，现在要求你在大草原上找一点P（Xp， Yp），使P点到任 一点Pi的距离Di与Wi之积之和为最小。 即求 D=W1*D1+W2*D2+…+Wi*Di+…+Wn*Dn 有最小值 结论：对x与y两个方向分别求解带权中位数，转化为一维。 设最佳点p为点k，则点k满足： 令W为点k到其余各点的带权距离之和，则 sigema( i=1 to k-1) Wi*Di <= W/2 sigema( i=k+1 to n) Wi*Di <= W/2 同时满足上述两式的点k即为带权中位数。

评论