빠른 이항 개수

기본 이항개수 알고리즘 

static int binomial(int n, int k) {      if(BI[n][k]>0){         return BI[n][k];      } else if(k==0 || n==k){         return BI[n][k] = 1;      } else         return BI[n][k] = (binomial(n-1, k-1) + binomial(n-1, k)) % MOD; }

BigIntger로 푸는 방법

public class boj2407 { static int N, M; static BigInteger BI[][]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine(), " "); N = Integer.valueOf(st.nextToken()); M = Integer.valueOf(st.nextToken()); BI = new BigInteger[1001][1001];  BigInteger big = new BigInteger("1"); BI[1][0] = BI[1][1] = big;                  for(int i=2;i<=N;i++) {             for(int j=0;j<=i;j++) {                 if(i == j || j == 0)                     BI[i][j] = big;                 else                     BI[i][j] = BI[i-1][j-1].add(BI[i-1][j]);             }         }         System.out.println(BI[N][M]); } }

빠른 이항계수 계산

static int mybi(int x, int y) {     if (!y)return 1;     if (y % 2)         return (x*mybi(x, y - 1)) % c;     return mybi((x * x) % c, y / 2) % c; }

재귀 호출되는 과정을 보면 y가 홀수일 때는 brute force와 같은 직접 곱해주는 방법을 사용합니다.

하지만 y가 짝수일 때 y를 2로 나누어주면서 x를 제곱한 수를 호출합니다.

이와같은 분할정복으로 pow(a,b)를 logb 시간에 해결해줄 수 있습니다.

있다고 하네용.. 흐흐흐 어렵당.