Combination calculation (Pascal's triangle) (Java)

Mathematical formula

The combination calculation can be mathematically expressed by the following formula.

nCr=\frac{n!}{r!{(n-r)!}}

Problems with the program

In programming, there are few cases where you are asked to combine by calculating according to the mathematical formula. The reason is that the factorial calculation of the numerator will cause ** overflow **.

n! = n\times(n-1)\times(n-2)\cdots2\times1

For example, just setting n = 13 will exceed the maximum value of int type and overflow. If n = 22, even long type will overflow. Therefore, it cannot be calculated according to the formula.

Therefore, it will be implemented by a calculation method that does not easily overflow. In this article, we will explain the calculation method using Pascal's triangle.

Calculation using Pascal's triangle

Pascal's triangle is shown in the figure below. [1] It can be created by writing the sum of two side-by-side numbers one step down in order from the top. It is known to correspond to the result of combination calculation, so we will use this.

In the program, Pascal's triangles are created in advance in a two-dimensional array, etc., and used as needed. When creating Pascal's triangle, the calculation is only addition, and there is no factorial calculation, so it is less likely to overflow than the formula.

[1] Quote from the figure http://www.mathlion.jp/article/ar103.html

Implementation example

Implement Pascal's triangle to the point where it can be created with a two-dimensional array. Write the first row in one array, the first row in one array, the second row in another array, and so on.

Fill in order from the top. As shown in the figure below, adding the upper element to the lower ** directly below and one to the right ** makes it a Pascal's triangle.

Other conditions -Computational complexity: Suppose you want to calculate up to about n = 2000 in nCr. -Overflow countermeasures: In problems that consider combinations, it is not uncommon for the answer itself to overflow as well as the calculation process, so the answer is as follows.

Calculate the answer and answer the remainder divided by 1000000007.

Here, it is implemented on the assumption that such overflow countermeasures are specified (that is, the correct implementation under the law of 1000000007). If no overflow countermeasure is specified, delete the line marked "Overflow countermeasure" in the comment.

Pascal_Array

        //Array preparation
		int c[][] = new int [2005][2005];//n=Create with a little margin so that you can make 2000 steps.

		//Pascal's triangle creation
		int mod = 1000000007;//Overflow protection: Specified in the problem.
		c[0][0]=1;//The top 1 is given as the initial value.
		for(int i=0;i<2003;i++) {//Turn the loop to make 2000 steps. I'm turning it with a little margin so that I don't have to think about the details.
			for(int j=0;j<2003;j++) {
				long tmp =  c[i][j]%mod;//Overflow measures
				c[i+1][j]+=tmp;
				c[i+1][j+1]+=tmp;
			}
		}

done. For example, if you want to find 5C2, you can get it with c [5] [2].

example

ABC132 D problem Blue and Red Balls https://atcoder.jp/contests/abc132/tasks/abc132_d