nCr mod p 구하기

1. O(N^2)  

 C[n][k] = C[n-1][k-1] + C[n-1][k] 

로 다이나믹 프로그래밍 합시다. 

#include <cstdio>
int dp[20][20];
int main(void){
    int n, m, k;
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n; i++)
    {
        dp[i][i] = 1;
        dp[i][0] = 1;
    }
    for (int i = 2; i <= n; i++)
        for (int j = 1; j < i; j++)
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
    printf("%d",dp[n][m]);
}

2. O(NlogP) 

페르마의 소정리를 알아야 하는데

즉, 

$a^{-1}\equiv a^{p-2}\left(\mathrm{mod}p\right)$

임. 증명은 http://freshrimpsushi.tistory.com/121 참고

ap−2를 구하면 되는데, 이는 분할정복으로 log (p-2)만에 구할 수 있음.

소스는 아래 참고

 
#define MOD 1000000007
int f[4000010];
int inv[4000010];
int mpow(int n, int p){
    if (p == 1) return n;
    int ret = mpow(n, p / 2);
    ret = (long long)ret * ret % MOD;
    if (p % 2) ret = (long long)n * ret % MOD;
    return ret;
}
void make_com(){
    inv[0] = inv[1] = f[0] = f[1] = 1;
    for (int i = 2; i <= 4000000; i++){
        f[i] = (long long)f[i - 1] * i % MOD;
    }
    for (int i = 2; i <= 4000000; i++){
        inv[i] = (long long)inv[i - 1] * mpow(i, MOD - 2) % MOD;
    }
}
int C(int n, int r){
    return (long long)f[n] * inv[r] % MOD * inv[n - r] % MOD;
}

참고로, n^p을 분할정복 하는 것은 여러 곳에서 많이 사용하는 로직임. 알아두면 도움이 될 것 

3. O(N)

쿠사가님의 블로그에서 봤는데, 솔직히 이해가 안가서 직접해 봄. 그랬더니 되더라...  코드 굉장히 짧음. 원본은 탑코더라고 합니다.

http://apps.topcoder.com/forums/?module=Thread&threadID=680416&start=15&mc=26 참고 

증명과 코드는 아래

inv(1) = 1

inv(i) = -(p / i) * inv(p % i)

증명은 아래와 같음

5) 

p mod p는 0임 따라서 없어짐.(p mod p * (1/(i*(p%i)))) mod p 를 분리한다고 생각하면 앞이 0이므로 뒤를 계산할 필요 없이 0임 멍청...) 

 분자 * (1/분모)로 분리한 후 각각 mod 붙인 것

6)  -floor(p/i) 는 p보다 작은 정수이므로 mod p 빼두 됨

inv(i) = -(p / i) * inv(p % i)

해서 이렇게 나옴

#include <cstdio>
#include <algorithm>
#define MOD 1000000007
#define SIZE 4000000
int f[SIZE +1];
int inv[SIZE+1 ];
void make_com(){
    inv[0] = inv[1] = f[0] = f[1] = 1;
    for (int i = 2; i <=SIZE ; i++)f[i] = 1LL*f[i - 1] * i % MOD;
    for (int i = 2; i <= SIZE ; i++)inv[i] = -1LL * (MOD / i) * inv[MOD % i] % MOD;
    for (int i = 2; i <= SIZE ; i++)inv[i] = 1LL * inv[i - 1] * ((inv[i] + MOD) % MOD) % MOD;
}
int C(int n, int r){return (long long)f[n] * inv[r] % MOD * inv[n - r] % MOD;}
int main(void){
    make_com();
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d", C(a, b));
}

이게 입사테스트에 나왔다는 이야기를 듣고... 정리합니다.

이해 안가는 부분은 덧글로

문제 참고

https://www.acmicpc.net/problem/11401

https://www.acmicpc.net/problem/11050