함수 nCrMod()

1 Java

자바 nCrMod() 문서를 참고하십시오.

Java

Copy

import java.math.BigInteger;
import java.util.*;
public class MyClass {
	static BigInteger nCrMod(int n, int r, int p) {
		long[] fact = new long[n+1];
		fact[0] = 1;
		for(int i=1; i<=n; i++) fact[i] = fact[i-1]*i % p;
		BigInteger P = BigInteger.valueOf(p);
		BigInteger A = BigInteger.valueOf(fact[n]);
		BigInteger B = BigInteger.valueOf(fact[r]).modInverse(P).remainder(P);
		BigInteger C = BigInteger.valueOf(fact[n-r]).modInverse(P).remainder(P);
		return A.multiply(B).multiply(C).remainder(P);
	}
	public static void main(String[] args) {
	    System.out.println( nCrMod(10,2,13) ); // 6
	    System.out.println( nCrMod(1000000,1,1234567891) ); // 1000000
	    System.out.println( nCrMod(1000000,100,1234567891) ); // 882875843
	    System.out.println( nCrMod(1000000,10000,1234567891) ); // 255162549
	    System.out.println( nCrMod(1000000,1000000,1234567891) ); // 1
	}
}

2 같이 보기

• 함수 nCr()