1. O(N^2)
C[n][k] = C[n-1][k-1] + C[n-1][k]
로 다이나믹 프로그래밍 합시다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | #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]); } | cs |
2. O(NlogP)
페르마의 소정리를 알아야 하는데
즉,
임. 증명은 http://freshrimpsushi.tistory.com/121 참고
ap−2를 구하면 되는데, 이는 분할정복으로 log (p-2)만에 구할 수 있음.
소스는 아래 참고
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | #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; } | cs |
참고로, 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)
해서 이렇게 나옴
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | #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)); } | cs |
이게 입사테스트에 나왔다는 이야기를 듣고... 정리합니다.
이해 안가는 부분은 덧글로
문제 참고
'Problem Solving > 이론' 카테고리의 다른 글
| Suffix Array (n(logn)(logn)) 풀이 맨버-마이어스의 알고리즘 (0) | 2016.10.25 |
|---|---|
| 거듭 제곱의 합 (2) | 2016.10.22 |
