数学中的一些公式在计算机科学中非常有用，今天说一下常用的一个公式：二项式定理。
二项式定理的最基本形式是： ( a + b ) n = C n 0 a n b 0 + C n 1 a n − 1 b 1 + C n 2 a n − 2 b 2 + . . . + C n n a 0 b n (a + b)^n = C_n^0a^nb^0+C_n^1a^{n-1}b^1+C_n^2a^{n-2}b^2+...+C_n^na^0b^n (a+b)n=Cn0anb0+Cn1an−1b1+Cn2an−2b2+...+Cnna0bn
由此可以得到两个重要的公式：
当a,b均等于1时， C n 0 + C n 1 + C n 2 + C n 3 + . . . + C n n = 2 n C_n^0+C_n^1+C_n^2+C_n^3+...+C_n^n = 2^n Cn0+Cn1+Cn2+Cn3+...+Cnn=2n， 也即 C n 1 + C n 2 + C n 3 + . . . + C n n = 2 n − 1 C_n^1+C_n^2+C_n^3+...+C_n^n = 2^n-1 Cn1+Cn2+Cn3+...+Cnn=2n−1当a=1时，有 C n 0 b 0 + C n 1 b 1 + C n 2 b 2 + . . . + C n n b n = ( 1 + b ) n C_n^0b^0+C_n^1b^1+C_n^2b^2+...+C_n^nb^n=(1+b)^n Cn0b0+Cn1b1+Cn2b2+...+Cnnbn=(1+b)n接下来让我们看一下其在算法题中的应用。
给定一个整数数组 A ，考虑 A 的所有非空子序列。
对于任意序列 S ，设 S 的宽度是 S 的最大元素和最小元素的差。
返回 A 的所有子序列的宽度之和。
由于答案可能非常大，请返回答案模 10^9+7。
示例： 输入：[2,1,3] 输出：6 解释： 子序列为 [1]，[2]，[3]，[2,1]，[2,3]，[1,3]，[2,1,3] 。 相应的宽度是 0，0，0，1，1，2，2 。 这些宽度之和是 6 。这个题目换个角度考虑的话，其实可以考虑每个数对结果的贡献，第i个数如果是一个区间的左边界，他就会使结果减去A[i]，如果是一个区间的右边界，那么他就会使最终结果加上A[i]。
那么问题就变成了，我们如何知道一个数作了多少次左边界，作了多少次右边界呢？
我们可以先排个序，排序完成后，第i个数如果要是一个左边界，那么与他构成子序列的数就都应该大于他，因此，作为左边界的次数就是从他右边的n-i-1个数中随机取大于一个数，根据我们的二项式定理的第一个常用结论，那么可能的次数为 2 n − i − 1 − 1 2^{n-i-1} -1 2n−i−1−1次，作为左边界的次数就是从他左边的i个数中随机取大于1个数，那么可能的次数就为 2 i − 1 2^i -1 2i−1，因此，这个数A[i]对于最终结果的贡献就是 A [ i ] ∗ ( 2 i − 1 − 2 n − i − 1 − 1 ) = A [ i ] ∗ ( 2 i − 2 n − i − 1 ) A[i]*(2^i - 1 -2^{n-i-1} -1)=A[i]*(2^i-2^{n-i-1}) A[i]∗(2i−1−2n−i−1−1)=A[i]∗(2i−2n−i−1)。
将所有数的贡献累加，就得到了结果。
小强是一个农场主，农场里有n头牛，每头牛有着独一无二的体重，每一头牛的颜色可能跟是m种颜色其中的一种，小强带了一些牛（可能为0个）出来吃草。你需要回答出小强带出来的牛的组合一共有多少种可能？
注意：因为一头牛有自己的体重（没有两头牛体重相等），所以如果四头牛的体重分别是1,2,3,4，颜色分别是y1,y2,y3,y4和另一种方案：四头牛的体重分别是1,2,3,4颜色分别是y1,y3,y2,y4即使两个方案的颜色的种类对应的数量是相同的，但是因为颜色对应的体重不同，所以是两个不同的方案。 由于方案书可能很大，请对1e9+7取模。
输入描述： 两个整数n,m(1≤n,m≤10^9) 输入： 3,2 输出： 27思路非常简单，我们先从n头牛中选取i头牛，然后给这i头牛上色，我们从0-n迭代i的值并累加结果，就得到了最终的方案数。
从n头牛中选取i头的方案数为 C n i C_n^i Cni，由于每头牛都是不一样的，因此给这i头牛上色的方案数为 m ∗ m ∗ m ∗ . . . ∗ m m*m*m*...*m m∗m∗m∗...∗m即i个m相乘， m i m^i mi，选牛与上色是独立的，符合乘法原理，因此选取i头牛的总方案数为 C n i m i C_n^im^i Cnimi，i的可能性为0-n，则总的可能方案数为 C n 0 m 0 + C n 1 m 1 + C n 2 m 2 + . . . + C n n m n C_n^0m^0+C_n^1m^1+C_n^2m^2+...+C_n^nm^n Cn0m0+Cn1m1+Cn2m2+...+Cnnmn，由二项式定理的第二个结论，可化简为 ( 1 + m ) n (1+m)^n (1+m)n，所以最终的结果即为 ( 1 + m ) n (1+m)^n (1+m)n。
