Problem Solving/이론

nCr mod p 구하기 2018.04.26 2
Suffix Array (n(logn)(logn)) 풀이 맨버-마이어스의 알고리즘 2016.10.25
거듭 제곱의 합 2016.10.22 2

nCr mod p 구하기

2018. 4. 26. 17:11

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]);
}
Colored by Color Scripter
cs

2. O(NlogP)

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

즉,

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

임. 증명은 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;
}
Colored by Color Scripter
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)

증명은 아래와 같음

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));
}
Colored by Color Scripter
cs

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

이해 안가는 부분은 덧글로

문제 참고

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

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

저작자표시 비영리 변경금지

'Problem Solving > 이론' 카테고리의 다른 글

Suffix Array (n(logn)(logn)) 풀이 맨버-마이어스의 알고리즘 (0)	2016.10.25
거듭 제곱의 합 (2)	2016.10.22

Suffix Array (n(logn)(logn)) 풀이 맨버-마이어스의 알고리즘

2016. 10. 25. 05:06

이사 중...

===============================================

아

하다가 멘탈 깨져서 정리함.

서픽스 어레이의 n^2logn 풀이는 아주 간단하다. 소스 코드만 정리해보자면 ...

1
2
3
4
5
6
7
8
9
10
vector<int> getSuffixArray(const string& s){
    vector<int> suffix; 
    //suffix배열을 초기화
    for (int i = 0; i < s.size(); ++i) suffix.push_back(i); 
    //문자열을 비교( 람다함수 사용 )
    sort(suffix.begin(), suffix.end(), [&s](int a, int b){
        return strcmp(s.c_str() + a, s.c_str() + b) < 0; 
    });
    return suffix; // 리턴
}
Colored by Color Scripter
cs
 

아아아아아주 쉽다. 오히려 람다함수가 더 어려운듯...

방식자체는 설명하자면 n개의 문자열을 죄다 때려박은 후
(메모리를 적게 사용하기 위해서 인덱스만 때려박음 : 4번째 줄)

그 해당 문자열을 정렬한다. 근데 정렬하는데 드는 비용이 nlogn이고 하나의 문자열을 비교하는 비용이 n이므로 n^2logn이다. 
굉장히 못써먹을 시간복잡도라고 생각할 수 있지만 사실 문자열을 비교하는데 일반적인 경우, 항상 n이 걸리지는 않기 때문에 그럭저럭 쓸만하다.
... 인풋이 aaaaaaaaaaaaaaaaaaaa... 만 아니라면... 

이것보다 좋은 알고리즘으로는 맨버-마이어스의 알고리즘이 있다. 
이 알고리즘의 시간복잡도는 n * log n * log n  n을 로그로 떨군건데 
난 멍청해서 이걸 이해하는데 엄청 오래걸렸다.
내가 구글링을 잘 못하는 걸 수도 있는데 제대로 정리된 블로그가 없어... 그래서 정리함. 




 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
std::vector<int> getSuffixArray(const string& s) {
    int n = s.size();
    
    //idx + t 까지 비교한다!
    int t = 1; 
 
    //group[i]는 t까지 비교했을 때 i의 그룹 번호 
    vector<int> group(n + 1);
    //t==0일때를 대신한 거라고 봐도 무방... 
    for (int i = 0; i < n; ++i) group[i] = s[i];
    group[n] = -1;
 
    //서픽스를 담을 배열
    vector<int> suffix(n);
    //서픽스를 초기화
    for (int i = 0; i < n; ++i) suffix[i] = i;
 
 
    while (t < n) {
 
        //비교함수 아주 중요함
        auto cmp = [&group, t](int a, int b){
            if (group[a] != group[b])
                return group[a] < group[b];
            return group[a + t] < group[b + t];
        };
 
        //정렬
        std::sort(suffix.begin(), suffix.end(), cmp);
 
        t *= 2;
 
        //t가 n보다 크거나 같으면 종료
        if (t >= n) break;
 
        //그룹 재지정
        vector<int> newGroup(n + 1);
        newGroup[n] = -1;
        newGroup[suffix[0]] = 0;
        for (int i = 1; i < n; ++i){
            if (cmp(suffix[i - 1], suffix[i])){
                newGroup[suffix[i]] = newGroup[suffix[i - 1]] + 1;
             }else
                newGroup[suffix[i]] = newGroup[suffix[i - 1]];
        }
        group = newGroup;
    }
    return suffix;
}
Colored by Color Scripter
cs
 


람다함수 [&group,t] <= group은 레퍼런스로 참조하고 t는 값을 복사해서 사용한다. 
나름대로 정리하자면 
s ? 구하려는 서픽스 배열의 target 스트링
group[i] ? i번째 접미사가 가지는 그룹 번호(index순) 
suffix[i] ? t까지 봤을때 i번째 접미사(사전 순)

t상태일때 어디까지 정렬되냐면 글자수가 2t일때까지 정렬된다.(즉 1일때는 글자수가 2개까지 정렬)
근데 이 그룹이라는 놈이 엄청나게 많은 것을 함축 하고 있는데 
group[a]는 사실 string의 [a...a+t)까지 비교한 결과의 상대 값이 저장되어 있다고 보면 된다.
이걸 이해하는데 이틀걸림. 

22~ 26줄의 compare함수를 보자. 

case : group[a] != group[b]
group[a]와 group[b]가 다를 때 group[a] < group[b]를 리턴한다. 
현재 t상태일때 벌써부터 group값이 다르다는 것은 이미 비교가 끝나있다는 것이다. 
그러니 a+t번째는 비교해볼 가치도 없음. 

case : group[a]와 group[b]가 같다.
string의 [a...a+t) [b...b+t)의 비교결과가 같다는 것이다. 
그럼이제 이걸 신경 쓸 필요가 없지.
[a+t...a+2t)와 [b+t...b+2t) 만 비교하면 된다. 
근데 이걸 일일이 다 비교하면 시간복잡도가 어마어마하게 증가한다. 
비교 할때마다 t만큼 추가 시간이 걸리니 말이다.
그리고 다행스럽게도 이 결과는 이미 저장되어 있다. 

어디에?
group[a+t]와 group[b+t]에!

그렇기 때문에 group[a+t]와 group[b+t]를 비교한 값을 리턴해주면 된다.

이 비교함수로 정렬이 완료되었으면 이제 이 결과를 다시 그룹에 반영해줘야 하는데 
이부분이 37~46줄이다. 
그룹의 값은 상대값이기 때문에 suffix의 첫번째 값은 0으로 설정하도록 하자. 
이제부터 suffix[n-1]까지 갱신해주는데 비교했는데 
이 비교의 기준은 이전 group과 t이다.(아직 갱신되기 전)
(실수로 t를 값이아니라 레퍼런스로 참조해봤는데 재밌는 일이 일어났다 ㅎㅎ)

case : suffix[i-1]과 suffix[i]를 비교
비교값이 더크데! <- 당연히 더 커야지 비교한 결과가... 
즉 이미 비교가 완료된 항목임.
그러니까 상대값도 1증가시켜줌. 
case : 현재까지 문자열을 사전순으로 비교할 수 없다. 
suffix배열은 t까지 진행했을때 정렬되어 있어야한다. 
즉 이부분은 아직 정렬이 제대로 이뤄지지 않았다는 것이고
따라서 아직까지는 suffix[i]와 suffix[i-1]은 누가더 사전순으로 우선인지 알 수 없다.
즉 suffix[i]와 suffix[i-1]은 길이가 2t일때까지 같았다는 것 
그룹번호를 같게 유지해서 다음 시퀀스에 비교할 수 있게 해두자.
(서픽스 어레이의 특성상 모든 문자열의 길이가 다르기때문에 같은건 존재할수없다.)

다른사람이 이해가 됐을지 모르겠다. 

내가 나중에 봤을때 이해할 수 있을 정도로만 정리해둔거라... 

틀린부분 있다면 지적부탁드려용.

참고 : 알고리즘 문제해결 전략 2권 suffix array파트 참조

p.s. suffix array관한 풀이는 최대 n까지 줄일 수 있고 이것보다 쉬운 nlogn풀이도 존재합니다.
p.s.2 그니까 저건 나중에 공부해서 포스팅할게요. 이거하는데도 지침 + sa와 한쌍인 lcp알고리즘도 다음에... 저가 너무 멍청해서