SGi's Blog

最近公共祖先（LCA）问题都应该很熟悉了。

LCA（T，u，v）：在有根树T中，询问一个距离根最远的结点x，使得x同时为结点u、v的祖先

LCA问题可以用朴素的DFS方法解决，但是时间复杂度就很高了，这里介绍一种高级一点的解决LCA问题的Tarjan算法。

Tarjan算法是由Robert Tarjan在1979年发现的一种高效的离线算法，也就是说，它要首先读入所有的询问（求一次LCA叫做一次询问），然后并不一定按照原来的顺序处理这些询问。

首先需要有一些预备知识：

1.基本图论

这个就不多讲了，如果有不知道的可以随便抓一本数据结构的书恶补一下。

2.并查集

并查集其实也是很简单的东西，实现的代码都不超过10行。

这里提一下并查集的概念，并查集是一种处理元素之间等价关系的数据结构，一开始我们假设元素都是分别属于一个独立的集合里的，主要支持两种操作：

1. 合并两个不相交集合(Union)
2. 判断两个元素是否属于同一集合(Find)

需要知道一点，就是并查集的Find操作的时间复杂度是常数级别的。

考察树T中所有与结点u有关的询问(u, v)

对于子树u中的结点v，满足LCA(u, v) = u

对于子树p1而非子树u中的结点v，满足LCA(u, v) = p1

对于子树p2而非子树p1中的结点v，满足LCA(u, v) = p2

算法DFS有根树T，定义从根节点到当前正在遍历的结点u的路径为活跃路径P
对于每个已经遍历过的结点x，我们用并查集将其连接到P上距离其最近的结点Find(x)

记录与u有关的询问集合为Q(u)

对于Q(u)中的任意一组询问LCA(u, v)，如果v已经遍历过，那么答案就是Find(v)，所以我们只需要维护当前所有以遍历结点的F即可。

第一次遍历结点u时，有Find(u) = u；
遍历完子树u后，子树u内任意结点v均有F(v) = u；回溯回结点p1时，子树u内任意结点v均有F(w) = p1，使用并查集完成即可。

算法流程：

Tarjan(u)
F(u)<-u；
For each (u,v) in Q(u) do Answer(u,v) <- F(v)
For each v in son(u)
a) Tarjan(v)；
b) F(v) <- u；

这里的F用并查集来实现。

这样LCA的Tarjan算法就可以完整的实现了，这个算法的时间复杂度取决于并查集Find操作的时间复杂度，如果采用不相交集森林的方法来实现并查集并采用路径压缩来优化，这样Find操作的时间复杂度可以认为是常数级别的。

所以Tarjan算法的时间复杂度就是O(Na(N) + Q)，a(N)在可以计算的范围内是一个小于4的常数，空间复杂度为O(N)，其中N表示问题规模，Q表示询问次数。

Problem 1: Bovine Bones [Rob Kolstad, 2008]

Bessie十分喜欢角色扮演游戏，所以他说服了Farmer John带她到Hobby Shop去，现在Bessie有三颗骰子，这些骰子分别有S1,S2,S3面。(2 <= S1 <= 20; 2 <= S2 <= 20; 2 <= S3 <= 40)
Bessie不停的扔啊扔，试图找出这三枚骰子最常出现的和是多少。
现在给出这三枚骰子各有几面，请你计算出这三个骰子最常出现的和是多少，如果不止一个和出现同样的次数，输出最小的那个和。
输入格式：
仅一行，S1,S2,S3用空格分隔
输出格式
仅一行，出现几率最高的和中最小的一个。
样例输入：
3 2 3
样例输出：
5
样例说明：
一下是所有可能出现的情况：
1 1 1 -> 3  1 2 1 -> 4  2 1 1 -> 4  2 2 1 -> 5  3 1 1 -> 5  3 2 1 -> 6
1 1 2 -> 4  1 2 2 -> 5  2 1 2 -> 5  2 2 2 -> 6  3 1 2 -> 6  3 2 2 -> 7
1 1 3 -> 5  1 2 3 -> 6  2 1 3 -> 6  2 2 3 -> 7  3 1 3 -> 7  3 2 3 -> 8
5和6都出现了5次，所以最终的答案是5。

Problem 2: Building A Fence [Jeffrey Wang, 2007]

勤奋的Farmer John想要建造一个由四面围成的栅栏来关住那些奶牛。他现在有一块长度为N(4 <= N <=2,500)的长木板，他需要把这块长木板切成边长均为正整数的四块，使得他能建造一个栅栏。
请问他有多少种不同的切割方式能使切割出来的木板围成一个四面的栅栏。
注意：
1.    不要考虑对称性的问题，不需要去除对称的方案和类似的复杂问题。
2.    栅栏围成的面积必须大于0
3.    结果可以用32位整数存储
输入格式：
仅一行，整数N
输出格式：
仅一行，Farmer John能将木板分割开来并能围成四边形的方案数。
样例输入：
6
样例输出：
6
样例解释：
Farmer John有10中方法将木板分成四块：(1, 1, 1,3); (1, 1, 2, 2); (1, 1, 3, 1); (1, 2, 1, 2); (1, 2, 2, 1); (1, 3,1, 1); (2, 1, 1, 2); (2, 1, 2, 1); (2, 2, 1, 1);(3, 1, 1, 1).
其中有四种情况是不能围成一个四边形的：(1, 1, 1, 3), (1, 1, 3, 1), (1, 3, 1, 1), (3,1, 1, 1)

Problem 3: Watering Hole [Paul Christiano, 2007]

Farmer John决定给他分别用1到N(1 <= N <= 300)分别编号的牧草浇水，他可以直接在一颗牧草旁边直接挖一口井来获得水，也可以用管子从任意有水的牧草那里来获得水。
在第i颗牧草旁边挖一口井的代价为Wi(1 <= W_i <= 100,000)，用管子连接第i与第j颗牧草的代价为Pij(1 <= Pij <=100,000; Pij = Pji; Pii=0)
请求出Farmer John浇灌这些牧草花费的最小代价。
输入格式：
第一行，一个整数N
第二行到第N+1行，行i+1表示Wi
第N+2行到第2N+1行，行N+1+i包含N个用空格分隔开来的整数，每行第j个数字即是Pij
输出格式：
仅一行，Farmer John浇灌这些牧草的最小代价。
样例输入：
4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0
样例输出：
9
样例解释：
总共有4颗牧草，在每个牧草旁边挖一口井的代价分别为1,4,4,3，每个点连接一根管子的价格用邻接矩阵给出。最优解为在第4颗牧草旁边挖一口井并把所有的牧草用连接起来，总代价为：3 + 2 + 2 + 2 = 9。

Problem 4: Pasture Walking [Neal Wu, 2007]

有N (2 <= N <= 1,000)头奶牛，分别编号为1到N。还有N颗牧草分别编号为1到N。简单起见，第i头奶牛都盯着第i颗牧草。
有几对牧草分别用一些小路连接了起来，总共有N-1条双向的小路，小路i连接了Ai及Bi颗牧草(1 <= Ai <= N; 1 <= Bi <= N)，小路的长度为Li (1 <= Li <= 10,000)
保证任意两颗牧草总能通过小路走到，也就是说这些小路构成了一棵树。
奶牛是群居性的动物，很喜欢串门。奶牛们会问你Q次问题(1 <= Q <= 1,000)，每次询问的内容很简单，就是从p1颗牧草到p2颗牧草最短的距离是多少。(1 <= p1 <= N; 1 <=p2 <= N)
输入格式：
第一行，两个用空格分隔的整数：N和Q
第二行到第N行，第i+1行包含三个用空格分隔的整数Ai,Bi,Li
第N+1行到第N+Q行，每行包含两个用空格分隔的整数p1,p2
输出格式：
共Q行，每行包含每次询问的最短距离的值。
输入样例：
4 2
2 1 2
4 3 2
1 4 3
1 2
3 2
输出样例：
2
7
样例解释：
询问1：1->2 总代价为2
询问2：3->4->1->2 总代价为7

Problem 5: Wheel Rotation [Fatih Gelgi, 2008]

Farmer John有一台老式的打谷机，需要在不同的齿轮上安装皮带来带动它工作。这个打谷机的引擎是1号滑轮顺时针转动，通过一根皮带带动2号滑轮转动，2号滑轮也通过皮带带动3号滑轮转动，依次类推，总共有N个滑轮，N-1根皮带(2 <= N <= 1,000)。

上面的这个图示给出了皮带的两种不同的连接方式，第一种成为直接连接，会被动滑轮与主动滑轮同向旋转，第二种成为交错连接，会使得被动滑轮反向旋转。
给出所有皮带的连接方式，已知1号滑轮是顺时针旋转的，请问第N号滑轮是怎么旋转的。
每条皮带用三个整数描述：
Si：皮带的主动轮编号
Di：皮带的被动轮编号
Ci：连接方式（0代表直接连接，1代表交错连接）
很不幸，Farmer John并不是按照序号依次给出这些数据的。

下面是一个N=4的例子，2与3之间使用直接连接，所以2和3都是顺时针旋转，3和4之间使用交错连接，所以4号滑轮是逆时针旋转的。

输入格式：
第一行，一个整数N
第二行到第N行，每行分别用三个整数Si,Di,Ci描述一条皮带。
输出格式：
仅一行，一个整数表示第N个滑轮的旋转方向，0代表顺时针，1代表逆时针。
样例输入：
4
2 3 0
3 4 1
1 2 0
样例输出：
1

Problem 6: Power Failure [Rob Kolstad, 2008]

一次严重的暴风雨破坏了一些农场电力网络的一些线路！Farmer John有一张包含(2 <= N <=
1,000)所有N个电线杆的地图，分别用1到N标号，每个电线杆都用一个有序数对(xi,yi)来表示(-100,000 <= x_i <=100000; -100,000 <= y_i <= 100,000)
有W (1 <= W <= 10,000)条电力线连接电线杆Pi与Pj (1 <= Pi <= N; 1 <= Pj <= N)
他需要从1号电线杆往N号电线杆输送电力（因为电力线路的损坏，可能需要通过一些中转的电线杆）
给出这N个电线杆和暴风雨后依然可用的电力线，请求出如果要恢复从1号电线杆到N号电线杆，所需要的连接的电力线长度的最小值，所有的电力线长度都可以用实数M (0.0 < M
<= 200,000.0)来表示。
下面左图是一个有9个电线杆和3条电力线的电力网，对于这个任务M=2.0，最好的恢复方案是连接4号与6号电线杆以及6号与9号电线杆。
After the storm              Optimally reconnected

1
2
3
4
5
6
7
8
9

3  . . . 7 9 . . . . .          3  . . . 7 9 . . . . .
                                          /
2  . . 5 6 . . . . . .          2  . . 5 6 . . . . . .
                                        /
1  2-3-4 . 8 . . . . .          1  2-3-4 . 8 . . . . .
   |                               |
0  1 . . . . . . . . .          0  1 . . . . . . . . .
 
   0 1 2 3 4 5 6 7 8 9             0 1 2 3 4 5 6 7 8 9

总长度： 1.414213562 + 1.414213562 = 2.828427124 .
输入格式：
第一行，用空格分隔的两个整数N,W
第二行，一个实数M
第三行到第N+2行，每行包含两个用空格分隔的整数xi,yi
第N+3行到第N+2+W行，每行包含两个用空格分隔的整数Pi,Pj
输出格式：
仅一行，一个整数，为最小电力线长度1000倍的整数部分，如果恢复方案不存在，输出-1。
样例输入：
9 3
2.0
0 0
0 1
1 1
2 1
2 2
3 2
3 3
4 1
4 3
1 2
2 3
3 4
样例输出：
2828

题目描述

source:vijos1012

。。。（省略一堆废话）
雍正将大致的情况告诉了你，并且说：大清一共有n个大城市，所有的大城市都不在同一个地点，同时我们对这n个城市从1到n进行编号；对于一个城市k，他有两个属性，一个是Xk，一个是Yk，分别表示这个城市所处的经度和纬度。请你告诉他问题的结果：L，即运河长度。（你可以假定地球是平面的）

输入

第1行，一个整数n。
从第2行到n+1行，按照i从小到大顺序，每行两个整数Xi，Yi，代表编号为i的城市的经度和纬度。
其中2<=n <=100000，1<=Xi,Yi<2^31。

输出

一个实数L（保留三位小数）

分析

题目简单的说就是给出平面上N个点，求最近点对，这题N有100000，直接做的后果就是这样：

编译通过…
├ 测试数据 01：运行超时…
├ 测试数据 02：运行超时…
├ 测试数据 03：运行超时…
├ 测试数据 04：运行超时…
├ 测试数据 05：运行超时…
├ 测试数据 06：运行超时…
├ 测试数据 07：运行超时…
├ 测试数据 08：运行超时…
├ 测试数据 09：运行超时…
├ 测试数据 10：运行超时…
————————-
Unaccepted 有效得分：0 有效耗时：0ms

可以容易想到两个优化：

1.按每个点的横坐标排序，枚举每个点的时候只要距离超过最小值就可以直接break

2.枚举的过程中，如果点i的横坐标和点j的横坐标的距离大于最小值也可以直接break

这样做的话，结果就会是这样：

编译通过…
├ 测试数据 01：答案正确… 9ms
├ 测试数据 02：答案正确… 40ms
├ 测试数据 03：答案正确… 9ms
├ 测试数据 04：答案正确… 0ms
├ 测试数据 05：答案正确… 87ms
├ 测试数据 06：答案正确… 9ms
├ 测试数据 07：答案正确… 25ms
├ 测试数据 08：答案正确… 150ms
├ 测试数据 09：答案正确… 0ms
├ 测试数据 10：答案正确… 118ms
————————-
Accepted 有效得分：100 有效耗时：447ms

这样这道题也算是解决了，其实这个问题还有更好的时间界，有两种都能达到O(nlogn)的时间

1.分治算法

用分治算法求S中最接近点对的基本思想是：选取一垂直线L∶x = m作为分割直线，将S的点分割为点数大致相同的2个子集S1和S2，使得：
S1={p∈S | p(x)≤m}，S2={p∈S | p(x)>m}
其中：m是S中各点x坐标的中位数，因此S1和S2中点数大致相同，且S=S1∪S2。递归地在S1和S2上解最接近点对的问题，分别得到 S1和S2中的最小距离d1和d2，并设d=min{d1,d2}。用P1和P2分别表示在直线L左边和右边与其距离在d范围的点构成的两个垂直长条平面区域。
P1：{p∈P1 | (|m-x(p)|≤d)}，P2：{p∈ P2 | (|x(p)-m|≤d)}
S中的最接近点对的距离或者是d，或者是某个{p,q}点对的距离，其中p∈P1，q∈P2。如果{p,q}是S中的最接近点对，则必有distance(p,q)
将上述描述简化如下：
（1）递归用L将节点集分成两个相等的部分；
（2）设d是d1和d2的最小值；
（3）删除离L超过d的节点；
（4）按照y维扫描剩下的节点，计算5个邻居的距离；
（5）如果距离小于d，更新d
下面我们分析分治算法的时间复杂度，由于步骤2-5是每个递归过程中都要去做的，我们先分析2-5。步骤2时间复杂度为O(1)；步骤3时间复杂度为O(n)；步骤4时间复杂度为O(1)；步骤5时间复杂度为O(1)，所以步骤2-5的时间复杂度为O(n)。步骤1递归地将平面S中的点分成两个相等的部分时间复杂度为O(logn)，所以总的时间复杂度为O(n)* O(logn)=O(nlogn)。

平面扫描算法

平面扫描算法用一根垂直的线从左扫到右。在扫描的过程中，需要维护遇到的最近的节点对以及它们之间的距离d；还需要维护一个区域D，D是一个矩形，右边界由下一个扫描到的点p确定，宽为已经扫描的点中的最近点对的距离。每次遇到下一个点p，我们就执行以下操作：
（1）将在x轴上离p的距离超过d的节点从D中删除掉；
（2）确定p左边离p最近的点q；
（3）如果q点和p之间的距离小于d，更新最近的节点对和d；
下面我们分析平面算法的时间复杂度。首先对所有点按x坐标排序，时间复杂度为O(nlogn)；其次在D中插入删除点，每次插入的时间复杂度为O(logn)，因为共有n个点，所以时间复杂度为O(nlogn)；然后比较p点的常数个邻居，时间复杂度为O(n)。所以平面扫描算法的时间复杂度为O(nlogn)。

PS：在Weiss的《数据结构与算法分析》有专门的一节来写了分治算法。

下面是AC Vijos1012的Pascal的程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

type
  dot = record x,y : extended; end;
 
var
  a : array[1..100000] of dot;
  n,i,j : longint;
  min,value : extended;
 
procedure qsort(l,r: longint);
var
  i,j: longint;
  y : dot;
  x : extended;
begin
  i:=l;
  j:=r;
  x:=a[(l+r) div 2].x;
  repeat
    while a[i].x < x do inc(i);
    while x < a[j].x do dec(j);
    if not(i>j) then begin
      y:=a[i];
      a[i]:=a[j];
      a[j]:=y;
      inc(i); dec(j);
    end;
  until i>j;
  if l<j then qsort(l,j);
  if i<r then qsort(i,r);
end;
 
function dist(a,b : dot):extended;
begin
  exit(sqrt(sqr(a.x-b.x) + sqr(a.y-b.y)));
end;
 
begin
  readln(n);
  for i := 1 to n do
    readln(a[i].x,a[i].y);
  qsort(1,n);
  min := maxlongint;
  for i := 1 to n do
    for j := i+1 to n do begin
      if a[j].x - a[i].x >= min then break;
      value := dist(a[i],a[j]);
      if value < min then begin
        min := value;
        break;
      end;
    end;
  writeln(min:0:3);
end.

题目描述

source:vijos1011,pku1088,SHTSC2002

Michael喜欢滑雪百这并不奇怪，因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子
1  2  3  4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9
一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-…-3-2-1更长。事实上，这是最长的一条。

输入

输入的第一行表示区域的行数R和列数C(1 <= R,C <= 100)。下面是R行，每行有C个整数，代表高度h，0<=h<=10000。

输出

输出最长区域的长度。

分析

这题直接用DFS裸搜肯定TLE，明显可以用DP来解决。
用opt[i,j]记录从点node[i,j]出发的最短路径
状态转移方程很容易写出来
opt[i,j]=max{opt[i+1,j],opt[i-1,j],opt[i,j+1],opt[i,j-1] } +1
但是这道题的状态并不容易表示，所以计算opt的时候需要类似DFS的方法，这就是DP的本质——记忆化搜索。

下面是过Vijos 1011的Pascal代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

const
  dx : array [1..4] of longint = (-1,0,1,0);
  dy : array [1..4] of longint = (0,1,0,-1);
 
var
  r,c,max,i,j,value : longint;
  node,opt : array[0..1000,0..1000] of longint;
 
function check(i,j : longint):boolean;
begin
  exit((i >= 1) and (i <= r) and (j >= 1) and (j<=c));
end;
 
function dp(i,j : longint):longint;
var
  k : longint;
begin
  if opt[i,j] > 0 then exit(opt[i,j]);
  for k := 1 to 4 do
    if check(i+dx[k],j+dy[k]) then
      if (node[i+dx[k],j+dy[k]] < node[i,j]) then
        if opt[i,j] < dp(i+dx[k],j+dy[k]) + 1 then
          opt[i,j] := dp(i+dx[k],j+dy[k]) + 1;
  exit(opt[i,j]);
end;
 
begin
  max := -maxlongint;
  fillchar(opt,sizeof(opt),0);
  readln(r,c);
  for i := 1 to r do begin
    for j := 1 to c do
      read(node[i,j]);
    readln;
  end;
 
  for i := 1 to r do
    for j := 1 to c do begin
      value := dp(i,j);
      if value > max then max := value;
    end;
  writeln(max+1);
end.

题目描述

source:vijos1400,zju1062,pku1095

小朋友cpc来到了恐龙之旅的出发点，遇到了一个非常恐怖的怪物。
怪物说：“你必须回答我出的一个问题，否则你就将被XXX”
可以用下面的方案给二叉树标号：
空树的序号为0。
只有一个根结点的树序号为1。
所有包含m个结点的二叉树的序号一定比任何一个包含m+1个结点的二叉树的序号小。
任何一棵二叉树其左子树序号为L，右子树序号为R，且它有m个结点，若它的序号为n，则所有序号大于n的且有m个结点的二叉树必满足下列条件之一：
—— 左子树序号大于L
—— 左子树序号等于L且右子树序号大于R

头5棵二叉树的形状如下：

你的任务就是对给定的序号，输出该序号所对应的二叉树。

输入格式

输入文件包含多组数据，每个数据只有一个单独的整数n（1<= n <=500,000,000）。当n=0时表示输入文件结束，但你不必输出n=0时的空树。

输出格式

对每个数据产生一个输出。每个数据仅须输出一行，表示对应序号的树。
输出树时使用下列格式：
一棵树若没有子树则输出根：X。
一棵树有左子树L和右子树R应当输出：(L’)X(R’)，L’和R’为序号L和R对应的二叉树。当然，若L=0则输出X(R’)；若R=0则输出(L’)X。

分析

N个结点的树有几种可以用Catalan数来求Cata(n)= C(2n,n)/(n+1)。

结点数：
N这整棵树总共有几个节点，用Cata(n)一个一个的依次减。减出来的数还得保留，因为接下去还得减。
左子树几个节点。要知道一个规律，当左子树有l个节点，右子树r个节点时，这样的树有几棵。答案是Cata(l)*Cata(r)。而且这树是按左子树的节点树依次排下来的。上面一样，一个一个挨个减下来。
算出来以后右子树也出来了。这就是左子树的节点数和右子树的结点数。

序号：
比如4,5,6,7,8。减到现在就是0,1,0,0,1。
0,1分别是2号和3号在他们那一组（2棵树的）里的序号。
设Serial(l)为左边的序列号（在他们那一组里的）Serial(r)为右边的，Cata(l),Cata(r)分别是左边/右边节点数树的总个数，t是N减到现在还剩的那个数。
则Serial(l) = t / Cata(r), Serial(r) = t  mod Cata(r)。
因为每棵树是从右开始排，填满了Cata(r) * Cata(l)种排法就结束，换到下一种Cata(r-1)的排法里去了，也不归这个排法的管了。左边就有Cata(l)种排法。

下面是Vijos上交的Pascal代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

type
  arr = array[0..18] of longint;
const
  a : arr = (1, 1, 2, 5, 14, 42, 132,429, 1430, 4862, 16796, 58786, 208012,742900, 2674440, 9694845, 35357670,129644790, 477638700);
var
  n : longint;
 
procedure print(idx,nodes : longint);
var
  i,j,temp,pos1,pos2 : longint;
begin
  temp := 0;
  if nodes = 1 then begin
    write('X');
    exit;
  end;
  for i := 0 to nodes-1 do begin
    inc(temp, a[i] * a[nodes-1-i]);
    if temp > idx then begin
      dec(temp, a[i] * a[nodes-1-i]);
      j := i;
      break;
    end;
  end;
  if j <> 0 then begin
    pos1 := (idx-temp) div a[nodes-1-j];
    write('(');
    print(pos1,j);
    write(')');
  end;
  write('X');
  if (nodes-1-j) <> 0 then begin
    pos2 := (idx-temp) mod a[nodes-1-j];
    write('(');
    print(pos2,nodes-1-j);
    write(')');
  end;
end;
 
procedure solve(n : longint);
var
  temp,nodes : longint;
begin
  temp:=0;
  nodes:=0;
  while temp<=n do begin
    inc(temp,a[nodes]);
    inc(nodes);
  end;
  dec(nodes);
  dec(temp,a[nodes]);
  dec(n,temp);
  print(n,nodes);
  writeln;
end;
 
begin
  readln(n);
  while n <> 0 do begin
    solve(n);
    readln(n);
  end;
end.

问题：求把n个球放入k个盒子中且每个盒子至少放一个球的方案总数。

球相同，盒子不同

方案数为C(n-1,n-m)
推广：如果可以有空盒，则方案数为C(n+m-1,n)

球相同，盒子相同

记方案数为f(n,m)
f(n,k)=f(n-1,k-1)+f(n-k,k)
f(n,0)=0(n>=1)
f(n,n)=1
对于所有的n<k，f(n,m)=0
考虑某一种方案，要么存在一个盒子里只放了1个球，要么所有盒子里都至少放了2个球

球不同，盒子相同

记方案数为S(n,k)
S(n,k)=k*S(n-1,k) + S(n-1,k-1)
S(n,1)=1(n>=1)
S(n,n)=1
对于所有的n<k，S(n,k)=0
(第二类Stirling数)
上面的递推式可以用组合证明：一方面，如果将元素1单独拿出来划分成1个集合，那么方法数是S(n-1,k-1)；另一方面，如果元素1所在的集合不止一个元素，那么可以先将剩下的n-1个元素划分好了以后再选一个集合把1放进去，方法数是k*S(n-1,k)；有加法原理得证。

球不同，盒子不同

方案数为S(n,k) * k!