本文涉及知识点证明容斥原理和证明集合枚举都用到了二项式定理【数学归纳法 组合数学】容斥原理基础知识位运算优先级位运算的结合性都是从左到右。优先级低的先运算。优先级位运算符说明7 位左移/位右移10按位与11^按位异或12按位或注意不同的编译系统的实现可能不同,所以加上括号保险。就算你把运算顺序牢记于心你的同事未必记得。异或xor ^ )定义x1⊕ \oplus⊕x2 y,对各二进制位分别运算如果x1和x2的某个二进制位不同异则y的此二进制位为1否则为0。性质一n个数的异或和积如果这n个数的某个二进制为1的数量是偶数则结果的此二进制位是0(偶数个1否则结果的此二进制为是1(奇数个1)。现在用数学归纳发证明a, {1,1}和{0,0}是偶数个1结果为0{1,0},{0,1} 奇数个1结果为1。b,假设n个数符合则n1个数也符合。将前两个数进行异或运算就符合假设了。推论一根据性质一可得如下推论n个数求异或积可以任意调换数的顺序结果不变。性质二0⊕ \oplus⊕x x性质三x⊕ \oplus⊕x 0性质四异或逆运算是其本身x1⊕ \oplus⊕x2 y ,则 y⊕ \oplus⊕x2 x1性质五x1⊕ \oplus⊕x2 x1 x2如果x1,x2的 所有的二进制位不同时为1,则 x1⊕ \oplus⊕x2 x1 x2否则 x1⊕ \oplus⊕x2 x1 x2习题n双m种筷子 遗失一只求遗失的一只长度。m值未知。已知2n-1只筷子的长度{a1,a2⋯ a 2 n − 2 , a 2 n − 1 \cdots a_{2n-2},a_{2n-1}⋯a2n−2,a2n−1}思路根据性质三答案就是这2n-1的数的异或积。位与()定义 x1 \Andx2 y。对二进制位分别运算x1和x2的某二进制位全部为1y对应的二进制位为1否则为0。性质一n个数依次位与结果为y如果这n个数的某二进制位全部为1,则y的对应二进制位为1否则为0。推论一根据性质一可得如下推论n个数求与积可以任意调换数的顺序结果不变。性质二(-1)x x性质三x1 \Andx2 y min(x1,x2)位或|定义 x1∨ \lor∨x2 y。对二进制位分别运算x1和x2的某二进制位全部为0y对应的二进制位为0否则为1。性质一n个数依次位与结果为y如果这n个数的某二进制位全部为0,则y的对应二进制位为0否则为1。推论一根据性质一可得如下推论n个数求与积可以任意调换数的顺序结果不变。性质二0∨ \lor∨x x性质三x1∨ \lor∨x2 max(x1,x2)取反~定义各二进制位0变1,1变0。位左移)、位右移()x n 相当于x× \times×2nx n 相当于 x÷ \div÷2n状态压缩用int mask的二进制位代替一个bool数组v此数组长度不超过31。第i位为1表示v[i]true第i位为0表示v[i]false。mask(1i) 表示mask第i为1。i∈ \in∈[0,31) 最低位i是0。以下操作只影响第i位不影响其它位。如果mask第i位无论是0还是1,设置为1 mask |(1i)如果mask第i位是无论是1还是0设置为0 mask ~(1i)将mask的第一位取反(0变1,1变0)。 mask ^(1 i子集状态压缩(枚举子集从大到小枚举mask的子集寻找下一个子集如果sub为0,没有比它小的子集。否则从右到左寻找第一个不为0的位假定此位是i1将i1位减1也就是变成0。i1后面的位取最大也就是mask的后i1位。sub-1 由于是从大到小枚举所以(sub-1)比i1高的位和mask一致。第i1位变成0。比i1位低的全为1。故mask(sub-1)就是 比sub小的最大子集。注意通过此方法枚举maxMask (1n)-1所有子集的子集的时间复杂度是O(3n)。下面利用二项式定理。0被maxMask 所有子集枚举共2n次。有且仅有一个二进位为1的数共有( n 1 ) n \choose 1(1n)个被2n-1个子集枚举。除当前位必须是1其它位01皆可。有且仅有2个二进位为1的数共有( n 2 ) n \choose 2(2n)个被2n-2个子集枚举。∑ i : 0 n ( n i ) 1 i 2 n − i ( 1 2 ) n 3 n 根据二项式定理 \sum_{i:0}^n{n \choose i}1^i2^{n-i}\\ (12)^n 3^n \quad 根据二项式定理i:0∑n(in)1i2n−i(12)n3n根据二项式定理常见的运算x是正整数(x-1) \Andx :将最低位的1设置成0。令第i1位是1如果有多位是1i1是最小的。比i1高的位i1位比第i1第的位x-1和x相同0全为1x不变1全为0比i1高的位两者完全相同故不变。i1位一个为1一个为1故为0。比i1低的为一个为1,一个为0故全为0。(-x) \Andx除最低位的1外全部置成0。负数存储的是补码反码1.令第i1位是1如果有多位是1i1是最小的。比i1高的位i1位比第i1第的位-x的反码和x相反0全为1-x的补码和x相反1全为0x的原码不变1全为0比i1高的位 x和-x相反故全为0。i1位x和-x都为1故结果为1。比i1低的位 x和-x都为0故结果为0。区间(子数组)位与位或模板vectorintnums;t r x l r n u m s [ x ] t_r \Large\And_{xl}^r nums[x]trxlrnums[x]集合s 记录所有的tr则s的元素数量最大31个。因为删除重复元素后tr的二进制1至少少1个。位或类似每个不重复的元素至少增加一个1。最大公约数也是如此。每次至少除以2。vectorvectorpairint,intvNumIndex(nums.size());for(inti0;inums.size();i){if(i){for(constauto[preNum,preIndex]:vNumIndex[i-1]){constintiNewpreNum|nums[i];if(vNumIndex[i].empty()||(vNumIndex[i].back().first!iNew)){vNumIndex[i].emplace_back(make_pair(iNew,preIndex));}else{vNumIndex[i].back().secondpreIndex;}}}if(vNumIndex[i].empty()||(vNumIndex[i].back().first!nums[i])){vNumIndex[i].emplace_back(make_pair(nums[i],i));}else{vNumIndex[i].back().secondi;}}vNumIndex[i]记录 nums[x…i]的异或值不重复及索引。重复值保留索引大的。x∈ \in∈[0,x]。第二个版本的模版classCRangCal{public:templateclass_Pr,classTintstaticvectorvectorpairT,intRangCal(constvectorTnums,_Pr pr){vectorvectorpairint,intvNumIndex(nums.size());for(inti0;inums.size();i){if(i){for(constauto[preNum,preIndex]:vNumIndex[i-1]){autoiNewpr(preNum,nums[i]);if(vNumIndex[i].empty()||(vNumIndex[i].back().first!iNew)){vNumIndex[i].emplace_back(make_pair(iNew,preIndex));}else{vNumIndex[i].back().secondpreIndex;}}}if(vNumIndex[i].empty()||(vNumIndex[i].back().first!nums[i])){vNumIndex[i].emplace_back(make_pair(nums[i],i));}else{vNumIndex[i].back().secondi;}}returnvNumIndex;}};0到x 1的数量class C1ToXBitCount{public:C1ToXBitCount(intiBitCount60):m_iBitCount(iBitCount){}longlongTotalBitCount(longlongx){autovBitCount(x);returnstd::accumulate(v.begin(),v.end(),0LL);}vectorlonglongBitCount(longlongx){vectorlonglongret(m_iBitCount);autocntx1;for(intbit0;bitm_iBitCount;bit){longlonghalfUnit(1LLbit);constautocurBitCountcnt/2/halfUnit*halfUnitmax(0LL,cnt%(2*halfUnit)-halfUnit);ret[bit]curBitCount;}returnret;}intm_iBitCount0;};BitCount的返回值v,v[i]表示0到x第i位1的数量。线性基(Linear Basis)某可重集合S任选若干数异或的结果集为f(S)求最小集合L,L⊆ \subseteq⊆S使得f ( L ) f ( S ) f(L)f(S)f(L)f(S)。如S{1,2,3},则L {1,2}。性质一异或的逆运算是本身。性质二如果S任意原始的最高位是M则f(S)任意元素的最高位一定不超过M。vector bit(M1,-1)。通过x以任意顺序枚举S。令x的最高位是m如果bit[m]是-1则bit[m] x操作一)即增加x否则x x ⊕ b i t [ m ] ( 操作二 ) 持续迭代。 x x \oplus bit[m](操作二)持续迭代。xx⊕bit[m](操作二)持续迭代。性质三S 的任意元素 x ∈ f ( L ) S的任意元素x\in f(L)S的任意元素x∈f(L)x迭代过程中操作一经过的m位m 1 , m 2 ⋯ m p {m_1,m_2 \cdots m_p}m1,m2⋯mp则x ⨁ i : 1 p b i t [ m i ] x\bigoplus_{i:1}^pbit[m_i]x⨁i:1pbit[mi]式子一性质四L中任意元素∈ f ( S ) \in f(S)∈f(S)。处理x时最多只增加一个元素。L的第一个元素是S的第一个非零元素。下面用数学归纳法证明。bit有q个元素是符合性质四则有q1个元素时也符合性质四。式子一⟺ b i t [ m p ] ⨁ i : 1 p − 1 b i t [ m i ] ⊕ x \iff bit[m_p] \bigoplus_{i:1}^{p-1}bit[m_i] \oplus x⟺bit[mp]⨁i:1p−1bit[mi]⊕x,x和m i m_imi都是f(S)中元素得证。查询最大异或值x 0m从大到小枚举bit[m]如果bit[m]存在且x此位为0则x ⊕ b i t [ m ] x \oplus bit[m]x⊕bit[m]x便是异或最大值。查询F(L)是否存在Xm从大到小枚举bit[m]如果x此位为0则忽略。如果bit[m]不存在返回false。否则x ⊕ b i t [ m ] x \oplus bit[m]x⊕bit[m]能够枚举完所有位返回真。时间复杂度O(logM)M是最大数。例题模板题【位运算】3097. 或值至少为 K 的最短子数组 II【动态规划 区间dp 位运算】3117. 划分数组得到最小的值之和【线段树 区间位运算模板】3117划分数组得到最小的值之和拆位法【位运算 拆位法 二分】3007. 价值和小于等于 K 的最大数字【位运算 拆位法】1835. 所有数对按位与结果的异或和试填法【位运算 试填法】【推荐】3022. 给定操作次数内使剩余元素的或值最小【位运算 反证法 试填法】2897.对数组执行操作使平方和最大子集状态压缩枚举子集【位运算 子集状态压缩】982按位与为零的三元组【位运算 状态压缩 枚举子集】1178. 猜字谜【动态规划】【子集状态压缩】LCP04 覆盖其它【位运算】【二分查找】【C算法】3007价值和小于等于 K 的最大数字【深度优化(DFS) 记忆化 位运算】2920收集所有金币可获得的最大积分【二分查找】【位运算】2354.优质数对的数目【数论】【分类讨论】【位运算】1611使整数变为 0 的最少操作次数【动态规划】【位运算】1787. 使所有区间的异或结果为零【位运算】【脑筋急转弯】2749. 得到整数零需要执行的最少操作数【数学】【位运算】LeetCoce810. 黑板异或游戏【位运算】【 数学】【 哈希映射】2857. 统计距离为 k 的点对【并集查找 图论 位运算】3108. 带权图里旅途的最小代价【位运算 贪心】2835. 使子序列的和等于目标的最少操作次数【数学归纳法】【位运算】【异或】3068最大节点价值之和扩展阅读算法为骨CAD为魂亲士工具箱支持中望CAD2024、AutoCad2013及以上多年承接CAD项目的精华工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作活到老学到老。明朝中后期大约50%的进士能当上堂官(副部及更高)能当上堂官的举人只有十余人。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。视频课程先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。https://edu.csdn.net/course/detail/38771如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程https://edu.csdn.net/lecturer/6176测试环境操作系统win7 开发环境 VS2019C17或者 操作系统win10 开发环境 VS2022C17如无特殊说明本算法用**C**实现。
C++位运算、状态压缩、枚举子集汇总
发布时间：2026/5/23 17:47:42
本文涉及知识点证明容斥原理和证明集合枚举都用到了二项式定理【数学归纳法 组合数学】容斥原理基础知识位运算优先级位运算的结合性都是从左到右。优先级低的先运算。优先级位运算符说明7 位左移/位右移10按位与11^按位异或12按位或注意不同的编译系统的实现可能不同,所以加上括号保险。就算你把运算顺序牢记于心你的同事未必记得。异或xor ^ )定义x1⊕ \oplus⊕x2 y,对各二进制位分别运算如果x1和x2的某个二进制位不同异则y的此二进制位为1否则为0。性质一n个数的异或和积如果这n个数的某个二进制为1的数量是偶数则结果的此二进制位是0(偶数个1否则结果的此二进制为是1(奇数个1)。现在用数学归纳发证明a, {1,1}和{0,0}是偶数个1结果为0{1,0},{0,1} 奇数个1结果为1。b,假设n个数符合则n1个数也符合。将前两个数进行异或运算就符合假设了。推论一根据性质一可得如下推论n个数求异或积可以任意调换数的顺序结果不变。性质二0⊕ \oplus⊕x x性质三x⊕ \oplus⊕x 0性质四异或逆运算是其本身x1⊕ \oplus⊕x2 y ,则 y⊕ \oplus⊕x2 x1性质五x1⊕ \oplus⊕x2 x1 x2如果x1,x2的 所有的二进制位不同时为1,则 x1⊕ \oplus⊕x2 x1 x2否则 x1⊕ \oplus⊕x2 x1 x2习题n双m种筷子 遗失一只求遗失的一只长度。m值未知。已知2n-1只筷子的长度{a1,a2⋯ a 2 n − 2 , a 2 n − 1 \cdots a_{2n-2},a_{2n-1}⋯a2n−2,a2n−1}思路根据性质三答案就是这2n-1的数的异或积。位与()定义 x1 \Andx2 y。对二进制位分别运算x1和x2的某二进制位全部为1y对应的二进制位为1否则为0。性质一n个数依次位与结果为y如果这n个数的某二进制位全部为1,则y的对应二进制位为1否则为0。推论一根据性质一可得如下推论n个数求与积可以任意调换数的顺序结果不变。性质二(-1)x x性质三x1 \Andx2 y min(x1,x2)位或|定义 x1∨ \lor∨x2 y。对二进制位分别运算x1和x2的某二进制位全部为0y对应的二进制位为0否则为1。性质一n个数依次位与结果为y如果这n个数的某二进制位全部为0,则y的对应二进制位为0否则为1。推论一根据性质一可得如下推论n个数求与积可以任意调换数的顺序结果不变。性质二0∨ \lor∨x x性质三x1∨ \lor∨x2 max(x1,x2)取反~定义各二进制位0变1,1变0。位左移)、位右移()x n 相当于x× \times×2nx n 相当于 x÷ \div÷2n状态压缩用int mask的二进制位代替一个bool数组v此数组长度不超过31。第i位为1表示v[i]true第i位为0表示v[i]false。mask(1i) 表示mask第i为1。i∈ \in∈[0,31) 最低位i是0。以下操作只影响第i位不影响其它位。如果mask第i位无论是0还是1,设置为1 mask |(1i)如果mask第i位是无论是1还是0设置为0 mask ~(1i)将mask的第一位取反(0变1,1变0)。 mask ^(1 i子集状态压缩(枚举子集从大到小枚举mask的子集寻找下一个子集如果sub为0,没有比它小的子集。否则从右到左寻找第一个不为0的位假定此位是i1将i1位减1也就是变成0。i1后面的位取最大也就是mask的后i1位。sub-1 由于是从大到小枚举所以(sub-1)比i1高的位和mask一致。第i1位变成0。比i1位低的全为1。故mask(sub-1)就是 比sub小的最大子集。注意通过此方法枚举maxMask (1n)-1所有子集的子集的时间复杂度是O(3n)。下面利用二项式定理。0被maxMask 所有子集枚举共2n次。有且仅有一个二进位为1的数共有( n 1 ) n \choose 1(1n)个被2n-1个子集枚举。除当前位必须是1其它位01皆可。有且仅有2个二进位为1的数共有( n 2 ) n \choose 2(2n)个被2n-2个子集枚举。∑ i : 0 n ( n i ) 1 i 2 n − i ( 1 2 ) n 3 n 根据二项式定理 \sum_{i:0}^n{n \choose i}1^i2^{n-i}\\ (12)^n 3^n \quad 根据二项式定理i:0∑n(in)1i2n−i(12)n3n根据二项式定理常见的运算x是正整数(x-1) \Andx :将最低位的1设置成0。令第i1位是1如果有多位是1i1是最小的。比i1高的位i1位比第i1第的位x-1和x相同0全为1x不变1全为0比i1高的位两者完全相同故不变。i1位一个为1一个为1故为0。比i1低的为一个为1,一个为0故全为0。(-x) \Andx除最低位的1外全部置成0。负数存储的是补码反码1.令第i1位是1如果有多位是1i1是最小的。比i1高的位i1位比第i1第的位-x的反码和x相反0全为1-x的补码和x相反1全为0x的原码不变1全为0比i1高的位 x和-x相反故全为0。i1位x和-x都为1故结果为1。比i1低的位 x和-x都为0故结果为0。区间(子数组)位与位或模板vectorintnums;t r x l r n u m s [ x ] t_r \Large\And_{xl}^r nums[x]trxlrnums[x]集合s 记录所有的tr则s的元素数量最大31个。因为删除重复元素后tr的二进制1至少少1个。位或类似每个不重复的元素至少增加一个1。最大公约数也是如此。每次至少除以2。vectorvectorpairint,intvNumIndex(nums.size());for(inti0;inums.size();i){if(i){for(constauto[preNum,preIndex]:vNumIndex[i-1]){constintiNewpreNum|nums[i];if(vNumIndex[i].empty()||(vNumIndex[i].back().first!iNew)){vNumIndex[i].emplace_back(make_pair(iNew,preIndex));}else{vNumIndex[i].back().secondpreIndex;}}}if(vNumIndex[i].empty()||(vNumIndex[i].back().first!nums[i])){vNumIndex[i].emplace_back(make_pair(nums[i],i));}else{vNumIndex[i].back().secondi;}}vNumIndex[i]记录 nums[x…i]的异或值不重复及索引。重复值保留索引大的。x∈ \in∈[0,x]。第二个版本的模版classCRangCal{public:templateclass_Pr,classTintstaticvectorvectorpairT,intRangCal(constvectorTnums,_Pr pr){vectorvectorpairint,intvNumIndex(nums.size());for(inti0;inums.size();i){if(i){for(constauto[preNum,preIndex]:vNumIndex[i-1]){autoiNewpr(preNum,nums[i]);if(vNumIndex[i].empty()||(vNumIndex[i].back().first!iNew)){vNumIndex[i].emplace_back(make_pair(iNew,preIndex));}else{vNumIndex[i].back().secondpreIndex;}}}if(vNumIndex[i].empty()||(vNumIndex[i].back().first!nums[i])){vNumIndex[i].emplace_back(make_pair(nums[i],i));}else{vNumIndex[i].back().secondi;}}returnvNumIndex;}};0到x 1的数量class C1ToXBitCount{public:C1ToXBitCount(intiBitCount60):m_iBitCount(iBitCount){}longlongTotalBitCount(longlongx){autovBitCount(x);returnstd::accumulate(v.begin(),v.end(),0LL);}vectorlonglongBitCount(longlongx){vectorlonglongret(m_iBitCount);autocntx1;for(intbit0;bitm_iBitCount;bit){longlonghalfUnit(1LLbit);constautocurBitCountcnt/2/halfUnit*halfUnitmax(0LL,cnt%(2*halfUnit)-halfUnit);ret[bit]curBitCount;}returnret;}intm_iBitCount0;};BitCount的返回值v,v[i]表示0到x第i位1的数量。线性基(Linear Basis)某可重集合S任选若干数异或的结果集为f(S)求最小集合L,L⊆ \subseteq⊆S使得f ( L ) f ( S ) f(L)f(S)f(L)f(S)。如S{1,2,3},则L {1,2}。性质一异或的逆运算是本身。性质二如果S任意原始的最高位是M则f(S)任意元素的最高位一定不超过M。vector bit(M1,-1)。通过x以任意顺序枚举S。令x的最高位是m如果bit[m]是-1则bit[m] x操作一)即增加x否则x x ⊕ b i t [ m ] ( 操作二 ) 持续迭代。 x x \oplus bit[m](操作二)持续迭代。xx⊕bit[m](操作二)持续迭代。性质三S 的任意元素 x ∈ f ( L ) S的任意元素x\in f(L)S的任意元素x∈f(L)x迭代过程中操作一经过的m位m 1 , m 2 ⋯ m p {m_1,m_2 \cdots m_p}m1,m2⋯mp则x ⨁ i : 1 p b i t [ m i ] x\bigoplus_{i:1}^pbit[m_i]x⨁i:1pbit[mi]式子一性质四L中任意元素∈ f ( S ) \in f(S)∈f(S)。处理x时最多只增加一个元素。L的第一个元素是S的第一个非零元素。下面用数学归纳法证明。bit有q个元素是符合性质四则有q1个元素时也符合性质四。式子一⟺ b i t [ m p ] ⨁ i : 1 p − 1 b i t [ m i ] ⊕ x \iff bit[m_p] \bigoplus_{i:1}^{p-1}bit[m_i] \oplus x⟺bit[mp]⨁i:1p−1bit[mi]⊕x,x和m i m_imi都是f(S)中元素得证。查询最大异或值x 0m从大到小枚举bit[m]如果bit[m]存在且x此位为0则x ⊕ b i t [ m ] x \oplus bit[m]x⊕bit[m]x便是异或最大值。查询F(L)是否存在Xm从大到小枚举bit[m]如果x此位为0则忽略。如果bit[m]不存在返回false。否则x ⊕ b i t [ m ] x \oplus bit[m]x⊕bit[m]能够枚举完所有位返回真。时间复杂度O(logM)M是最大数。例题模板题【位运算】3097. 或值至少为 K 的最短子数组 II【动态规划 区间dp 位运算】3117. 划分数组得到最小的值之和【线段树 区间位运算模板】3117划分数组得到最小的值之和拆位法【位运算 拆位法 二分】3007. 价值和小于等于 K 的最大数字【位运算 拆位法】1835. 所有数对按位与结果的异或和试填法【位运算 试填法】【推荐】3022. 给定操作次数内使剩余元素的或值最小【位运算 反证法 试填法】2897.对数组执行操作使平方和最大子集状态压缩枚举子集【位运算 子集状态压缩】982按位与为零的三元组【位运算 状态压缩 枚举子集】1178. 猜字谜【动态规划】【子集状态压缩】LCP04 覆盖其它【位运算】【二分查找】【C算法】3007价值和小于等于 K 的最大数字【深度优化(DFS) 记忆化 位运算】2920收集所有金币可获得的最大积分【二分查找】【位运算】2354.优质数对的数目【数论】【分类讨论】【位运算】1611使整数变为 0 的最少操作次数【动态规划】【位运算】1787. 使所有区间的异或结果为零【位运算】【脑筋急转弯】2749. 得到整数零需要执行的最少操作数【数学】【位运算】LeetCoce810. 黑板异或游戏【位运算】【 数学】【 哈希映射】2857. 统计距离为 k 的点对【并集查找 图论 位运算】3108. 带权图里旅途的最小代价【位运算 贪心】2835. 使子序列的和等于目标的最少操作次数【数学归纳法】【位运算】【异或】3068最大节点价值之和扩展阅读算法为骨CAD为魂亲士工具箱支持中望CAD2024、AutoCad2013及以上多年承接CAD项目的精华工作中遇到的问题可以按类别查阅鄙人的算法文章请点击《算法与数据汇总》。学习算法按章节学习《喜缺全书算法册》大量的题目和测试用例打包下载。重视操作活到老学到老。明朝中后期大约50%的进士能当上堂官(副部及更高)能当上堂官的举人只有十余人。子墨子言之事无终始无务多业。也就是我们常说的专业的人做专业的事。视频课程先学简单的课程请移步CSDN学院听白银讲师也就是鄙人的讲解。https://edu.csdn.net/course/detail/38771如何你想快速形成战斗了为老板分忧请学习C#入职培训、C入职培训等课程https://edu.csdn.net/lecturer/6176测试环境操作系统win7 开发环境 VS2019C17或者 操作系统win10 开发环境 VS2022C17如无特殊说明本算法用**C**实现。
