本节书摘来自异步社区《趣题学算法》一书中的第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 K4 do item←(itemxi) MOD 201007135 count←(count+item) MOD 201007136 return7 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 ← p12 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研读，并试运行之。
相关资源：趣题学算法.徐子珊(带书签高清文字版).pdf