《趣题学算法》—第1章1.3节加法原理和乘法原理

本节书摘来自异步社区《趣题学算法》一书中的第1章1.3节加法原理和乘法原理，作者徐子珊,更多章节内容可以访问云栖社区“异步社区”公众号查看。

1.3　加法原理和乘法原理
组合数学中有两条著名的原理——加法原理和乘法原理。利用这两条原理可以快速地解决一些计数问题。

加法原理：做一件事，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，……，在第n类办法中有mn种不同的方法，那么完成这件事共有N＝m1＋m2＋m3＋…＋mn种不同方法。

乘法原理：做一件事，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，……，做第n步有mn种不同的方法，那么完成这件事共有N＝m1×m2×m3×…×mn种不同的方法。
维基百科

冒泡排序是一种非常简单的排序算法，其运行时间为O(n2)。每趟操作从列表首开始，以此比较相邻项，需要时交换两者。重复进行若干趟这样的操作直至无需再做任何交换操作为止。假定恰好做了T趟操作，序列就按升序排列，我们就说T为对此序列的冒泡排序趟数。下面是一个例子。序列为“5 1 4 2 8”，对其施行的冒泡排序如下所示。

第一趟操作：

( 51 4 2 8 ) −> ( 1 5 4 2 8 )，比较头两个元素，并将其交换。

( 1 5 4 2 8 ) −> ( 1 4 5 2 8 )，交换，因为5 > 4。

( 1 4 5 2 8 ) −> ( 1 4 2 5 8 )，交换，因为5 > 2。

( 1 4 2 5 8 ) −> ( 1 4 2 5 8 )由于这两个元素已经保持顺序（8>5），算法不对它们进行交换。

第二趟操作：

( 1 4 2 5 8 ) −> ( 1 4 2 5 8 )

( 1 4 2 5 8 ) −> ( 1 2 4 5 8 )，交换，因为4 > 2。

( 1 2 4 5 8 ) −> ( 1 2 4 5 8 )

( 1 2 4 5 8 ) −> ( 1 2 4 5 8 )

在T = 2趟后，序列已经排好序，所以我们说对此序列冒泡排序的趟数为2。

ZX在算法课中学习冒泡排序，他的老师给他留了一个作业。老师给了ZX一个具有N个两两不等的元素的数组A，并且已经排成升序。老师告诉ZX，该数组是经过了K趟的冒泡排序得来的。问题是：A有多少种初始状态，使得对其进行冒泡排序，趟数恰为K？结果可能是一个很大的数值，你只需输出该数相对于模20100713的剩余。

输入

输入包含若干个测试案例。

第一行含有一个表示案例数的整数T (Tleqslant100 000)。

跟着的是T行表示各案例的数据。每行包含两个整数N和K(1leqslantNleqslant1,000,000, 0leqslantKleqslantN−1)，其中N表示序列长度而K表示对序列进行冒泡排序的趟数。

输出

对每个案例，输出序列的初始情形数对模20100713的剩余，每个一行。

输入样例

3
3 0
3 1
3 2

输出样例

1
3
2

解题思路

（1）数据的输入与输出

根据输入文件格式的描述，首先在其中读出测试案例个数T。然后依次读取案例数据N和K。对每个案例计算进行K趟处理就能实现冒泡排序的数组A[1..N]有多少种可能的初始状态，并将所得结果作为一行写入输出文件。

1 打开输入文件inputdata
2 创建输出文件outputdata
3 从inputdata中读取案例数T
4 for t←1 to T
5   do 从inputdata中读取案例数据N, K
6      BUBLLE-SORT-ROUNDS(N, K, k, x, count)
7      将count作为一行写入outputdata中
8 关闭inputdata
9 关闭outpudata

其中，第6行调用过程BUBLLE-SORT-ROUNDS(N, K, k, x, count)计算进行K趟处理就能实现冒泡排序的数组A[1..N]有多少种可能的初始状态，是解决一个案例的关键。

（2）处理一个案例的算法过程

为方便计，我们假定序列A中的N个数为0，1，…，N-1。注意，冒泡排序的第k趟操作，总是将当前范围（A[0..k−1]）内的最大的元素推至当前范围的最后位置A[k−1]。

除了针对趟数K=0的唯一初始状态A[0..N−1]已经有序外，我们归纳K=k(1leqslantk

K=1时，初始状态只能是1，…， N−1中的一个元素不出现在自己应有的位置上，而其他元素均处于相对顺序的位置上。对于1而言，它要出现在A[0]处；对于2而言，它可以出现在A[0]、A[1]处之一；…一般地，对于i（0

K=2时，初始状态可以是1，…， N−1中的两个元素不出现在应有的位置上，而其他元素均处于相对顺序的位置上。对于0

一般地，K=k(1leqslantk

若将1～N-1中的K个数0

**BUBLLE-SORT-ROUNDS(N, K, k, x, count) ▷k表示递归层次
1 if kgeqslantK ▷得到一个积
2 then item←1
3 for i←1 to K
4 do item←(itemxi) MOD 20100713
5 count←(count+item) MOD 20100713
6 return
7 if k=0
8 then begin←N-1, end← K ▷顶层，x[0]的取值范围
9 else begin←xk-1-1, end← K-k ▷k>1时，x[k]的取值范围
10 for p←begin downto end ▷确定第k个因子
11 do xk ← p
12 BUBLLE-SORT-ROUNDS(N, K, k+1)**
算法1-10　计算具有N个不同元素恰做K趟操作完成排序的序列初始状态数的过程

对测试案例数据N和K，上述过程运行如下。这是一个递归过程。递归层次由参数k表示，表示计算一个积中第k个因子。最顶层的调用应该是BUBLLE-SORT-ROUNDS(N, K, 0, x, count)，即k=0。

第1～7行当检测到k>K时，意味着得到一个积的所有因子。由于20100713是一个素数，以它为模的剩余类[3]对加法和乘法运算是封闭的，所以，可以对每一步乘法运算求关于模20100713的剩余，也可以在将积累加到count时进行求关于模20100713的剩余。

第7～8行if-then-else结构针对k是否为1决定第k个因子的取值范围begin～end。

第9～12行的for循环完成对第k个因子xk的确定后，调用自身确定xk+1。

由于sum{_{1<{{i}_{1}}

解决本问题的算法的C++实现代码存储于文件夹laboratory/Bubble Sort中，读者可打开文件BubbleSort.cpp研读，并试运行之。