Processing math: 100%
반응형

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

 

13977번: 이항 계수와 쿼리

M개의 자연수 N과 정수 K가 주어졌을 때 이항 계수 (NK)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽어보시는 걸 추천드립니다.

 

https://rudalsd.tistory.com/61?category=1064608 

 

[ 알고리즘 ] 페르마의 소정리(Fermat's little theorem)

페르마의 소정리(Fermat's little theorem)는 다음과 같이 정리할 수 있습니다. a≥0에 대하여 ap≡a(mod p)를 만족하고, 만약 p가 소수이고, a와 p가 서로소이면 ap−1≡1(mod..

rudalsd.tistory.com

 

먼저 (NK)는 다음과 같이 나타낼 수 있습니다.

 

(NK)=N!(N−K)!K!

 

그리고 페르마의 소정리를 이용하여 mod m에서 어떤 수를 a로 나눈다는 뜻은 a의 역원을 곱한다는 뜻과 같습니다. 따라서 m이 소수일 때, am−1≡1(mod m)이고, a×am−2≡1(mod m)이므로 mod m에서 a에 대한 곱셈의 역원은 am−2입니다.

 

따라서, 

 

N!(N−K)!K!≡N!×((N−K)!K!)m−2(mod m)

 

이 됩니다.

 

분모의 수로 나누는 방법 대신 m−2제곱한 값을 곱해주면 모듈러 연산 시 같은 결과가 나오는 것을 알 수 있습니다.

이 때 m의 값이 1,000,000,007로 매우 크므로 분할 정복을 이용한 거듭제곱을 이용하여 문제를 풀어주면 됩니다.

 

 

[ 소스 코드 ]

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
#include<iostream>
 
#define ll long long
#define MOD 1000000007
 
using namespace std;
 
ll fac[4000001];
 
int M, N, K;
 
ll pow(ll num, int p)        //분할 정복을 이용한 거듭제곱
{
    if (p == 0) return 1;
    if (p == 1) return num;
 
    if (p % 2 == 0) {
        ll temp = pow(num, p / 2);
        temp %= MOD;
        return (temp * temp) % MOD;
    }
    else {
        ll temp = pow(num, p - 1);
        temp %= MOD;
        return (num * temp) % MOD;
    }
}
 
int main()
{
    fac[0] = 1;
 
    for (int i = 1; i <= 4000000; i++) {
        fac[i] = fac[i - 1] * i;
        fac[i] %= MOD;
    }
 
    scanf("%d", &M);
 
    for (int i = 0; i < M; i++) {
        scanf("%d %d", &N, &K);        //페르마의 소정리
        ll ans = (fac[N] * pow((fac[N - K] * fac[K]) % MOD, MOD - 2)) % MOD;
        printf("%lld\n", ans);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 17371번 - 이사 (C++)  (0) 2022.07.14
[ 백준 ] 14428번 - 수열과 쿼리 16 (C++)  (0) 2022.07.13
[ 백준 ] 11689번 - GCD(n, k) = 1 (C++)  (0) 2022.07.11
[ 백준 ] 3015번 - 오아시스 재결합 (C++)  (0) 2022.07.10
[ 백준 ] 11505번 - 구간 곱 구하기 (C++)  (0) 2022.07.09
반응형

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

 

11689번: GCD(n, k) = 1

자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽어보시는 걸 추천드립니다!

https://rudalsd.tistory.com/59?category=1064608 

 

[ 알고리즘 ] 오일러 피 함수(Euler's phi function)

오일러 피(파이) 함수(Euler's phi function)는 1부터 n까지의 정수 중 n과 서로소인 수의 개수를 구하는 함수이고, Ф(n)으로 표현합니다. 이때, 서로소는  1 이외에 공약수를 갖지 않는 둘 이상의 양의

rudalsd.tistory.com

 

위의 공식을 이용하여 ans에 n을 대입한 후 n에 대하여 어떠한 수 i로 나누어지면 ans = ans - ans / i를 통해서 답을 구할 수 있습니다.

 

이때 i * i <= n까지 구하는 이유는 n의 제곱근은 i보다 작거나 같기때문입니다.

 

하지만 마지막에 n이 1이 아니라면 남은 n은 소수이므로 n이 1이 아닐 때 마지막으로 ans = ans - ans / 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
#include<iostream>
 
#define ll long long
 
using namespace std;
 
ll n;
ll ans;
 
int main()
{
    cin >> n;
    ans = n;
 
    for (ll i = 2; i * i <= n; i++) {
        int cnt = 0;
        bool flag = false;
        while (n % i == 0) {        //소인수분해
            n /= i;
            flag = true;
        }
 
        if (flag) {        //오일러 피
            ans = ans - ans / i;
        }
    }
 
    if (n != 1) {        //남은 n이 소수라면
        ans = ans - ans / n;
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 14428번 - 수열과 쿼리 16 (C++)  (0) 2022.07.13
[ 백준 ] 13977번 - 이항 계수와 쿼리 (C++)  (0) 2022.07.12
[ 백준 ] 3015번 - 오아시스 재결합 (C++)  (0) 2022.07.10
[ 백준 ] 11505번 - 구간 곱 구하기 (C++)  (0) 2022.07.09
[ 백준 ] 2096번 - 내려가기 (C++)  (0) 2022.07.08
반응형

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

 

1019번: 책 페이지

첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

책의 페이지가 N이라고 할 때 1~N까지 0 ~ 9가 몇 번 나오는지 출력하는 문제입니다. N의 최댓값이 1,000,000,000이므로 모든 숫자를 탐색하면 시간 초과가 나므로 구간을 정해 답을 구하는 방법을 통해 문제를 풀었습니다.

 

A ~ B까지 숫자 중 0 ~ 9까지의 숫자가 몇번 나오는지 구하는 방법은 다음과 같습니다.

 

A는 일의 자리가 0이 되어야하고, B는 일의 자리가 9가 되어야 합니다. 그러기 위해서 A는 값을 더해주어 일의 자리를 0으로 맞춰주고, B는 값을 빼주어 일의 자리를 9로 맞춰줍니다.

 

A = 1345, B = 8742 라고 할 때, A에는 값을 더해주어 1350으로 만들고, B에는 값을 빼주어 8739로 맞춰줍니다. 이때 A부터 B까지 일의 자리에 0~9는 총 (8739 / 10 - 1350 / 10 + 1)번 등장합니다. 즉, (873 - 135 + 1)번 등장합니다. 그리고 1345~1349, 8740~8742까지 0~9이 몇 번 나오는지 따로 체크해주어야 합니다.

 

이제 일의 자리에 0~9가 몇 번 나오는지 구했습니다. 다음으로 십의 자리에 0~9가 몇번 나오는지 구해보겠습니다.

 

이때 A = 135, B = 873 입니다. 똑같은 방식을 적용하면 A = 140, B = 869로 바꾸어주고, 이 때 0~9는 (86 - 14 + 1)번 나올까요? 아닙니다!! 십의 자리 숫자이기 때문에 10을 곱해주어야 합니다. 따라서 (86 - 14 + 1) * 10을 각각 더해주면 됩니다.

 

똑같은 방식으로 천의 자리, 만의 자리 등등 구해주시면 됩니다.

 

다만 A = 7, B = 15 일 때, 똑같은 방식을 적용하면 A = 10, B = 9가 되므로 A의 값이 더 커지게 됩니다. 이 때는 B + 1부터 15까지의 0~9의 개수를 구해주고, A/10( = 1)부터 9까지 다시 구해주시면 됩니다.

 

[ 소스 코드 ]

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<iostream>
#include<string>
 
using namespace std;
 
int N;
int cnt[10];
 
int NtoA(int num)        //num보다 작은 가장 큰 10^n 수
{
    int digit = 1;
    while (1) {
        digit *= 10;
        if (num < digit) {
            return digit / 10;
        }
    }
}
 
int NtoB(int num)        //num보다 작은 가장 큰 9로 끝나는 수
{
    if (num < 9) {
        return num;
    }
    while (1)
    {
        if (num % 10 == 9) {
            return num;
        }
        num--;
    }
}
 
void AtoN(int A, int N, int digit)        //A부터 N까지의 수의 1의 자리 숫자의 개수 구하기
{
    if (N < 10) {
        for (int i = A; i <= N; i++) {
            cnt[i] += digit;
        }
        return;
    }
    int B = NtoB(N);
    for (int i = B + 1; i <= N; i++) {
        string str = to_string(i);
        for (int j = 0; j < str.size(); j++) {
            cnt[str[j] - '0'] += digit;
        }
    }
 
    for (int i = 0; i < 10; i++) {
        cnt[i] += (B / 10 - A / 10 + 1) * digit;
    }
 
    AtoN(A / 10, B / 10, digit * 10);
}
 
int main()
{
    cin >> N;
 
    int A = NtoA(N);
    int B = NtoB(N);
 
    if (A > B) {
        for (int i = B + 1; i <= N; i++) {
            string str = to_string(i);
            for (int j = 0; j < str.size(); j++) {
                cnt[str[j] - '0']++;
            }
        }
        A /= 10;
        AtoN(A, B, 1);
    }
    else {
        AtoN(A, N, 1);
    }
 
    while (1)
    {
        if (A == 1) {
            break;
        }
        AtoN(A / 10, A - 1, 1);
        A /= 10;
    }
 
    for (int i = 0; i < 10; i++) {
        cout << cnt[i] << " ";
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 2357번 - 최솟값과 최댓값 (C++)  (0) 2022.07.05
[ 백준 ] 2042번 - 구간 합 구하기 (C++)  (0) 2022.07.04
[ 백준 ] 17436번 - 소수의 배수 (C++)  (0) 2022.07.02
[ 백준 ] 16565번 - N포커 (C++)  (0) 2022.07.01
[ 백준 ] 15824번 - 너 봄에는 캡사이신이 맛있단다 (C++)  (0) 2022.06.30
반응형

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

 

17436번: 소수의 배수

첫째 줄에 N(1 ≤ N ≤ 10)과 M(1 ≤ M ≤ 1012)이 주어진다. 둘째 줄에는 N개의 소수가 주어진다. 입력으로 주어지는 소수는 100보다 작거나 같으며, 같은 소수가 두 번 이상 주어지지 않는다.

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제에서는 포함 배제의 원리를 활용해 문제를 풀어야 하므로 다음 글을 일고 오시면 좋습니다!

 

https://rudalsd.tistory.com/47?category=1064608 

 

[ 알고리즘 ] 포함 배제의 원리(Inclusion–exclusion principle)

오늘은 포함 배제의 원리(Inclusion-exclusion principle)에 대해 설명드리겠습니다. 유한한 집합의 합집합의 총 원소의 개수를 세는 방법입니다. [ 동작 원리 ] 즉, 겹치는 집합의 개수가 홀수이면 해당

rudalsd.tistory.com

 

N의 최댓값이 10이므로 모든 경우의 수를 생각해도 O(2^10)이므로 0.25초 안에 충분히 풀 수 있습니다.

 

배열에 소수들을 저장하고, 각 조합의 소수들을 모두 곱한 값으로 M을 나누어 준 몫을 답에 더해주거나 빼주면 됩니다. M보다 작은 값들 중 나누어 떨어지는 수가 몫의 개수만큼 있다는 뜻이기 때문입니다. 만약 조합의 개수가 홀수라면 더해주고, 짝수라면 빼주면 됩니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<vector>
 
using namespace std;
 
int N;
long long M;
int arr[10];
 
int main()
{
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    long long ans = 0;
 
    for (int i = 1; i < (1 << N); i++) {
        int cnt = 0;
        long long num = 1;
        for (int j = 0; j < N; j++) {
            if (i & (1 << j)) {
                cnt++;        //몇 개의 소수가 곱해져 있는지
                num *= arr[j];    //소수들을 곱함
            }
        }
 
        if (cnt % 2 == 1) {
            ans += M / num;        //M을 소수들을 모두 곱한 값으로 나눈 값을 더함
        }
        else {
            ans -= M / num;        //M을 소수들을 모두 곱한 값으로 나눈 값을 뺌
        }
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 2042번 - 구간 합 구하기 (C++)  (0) 2022.07.04
[ 백준 ] 1019번 - 책 페이지 (C++)  (0) 2022.07.03
[ 백준 ] 16565번 - N포커 (C++)  (0) 2022.07.01
[ 백준 ] 15824번 - 너 봄에는 캡사이신이 맛있단다 (C++)  (0) 2022.06.30
[ 백준 ] 13334번 - 철로 (C++)  (0) 2022.06.29
반응형

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

 

16565번: N포커

첫째 줄에 N장의 카드를 뽑았을 때, 플레이어가 이기는 경우의 수를 10,007로 나눈 나머지를 출력하라.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제에서는 포함 배제의 원리를 활용해 문제를 풀어야 하므로 다음 글을 일고 오시면 좋습니다!

 

https://rudalsd.tistory.com/47?category=1064608 

 

[ 알고리즘 ] 포함 배제의 원리(Inclusion–exclusion principle)

오늘은 포함 배제의 원리(Inclusion-exclusion principle)에 대해 설명드리겠습니다. 유한한 집합의 합집합의 총 원소의 개수를 세는 방법입니다. [ 동작 원리 ] 즉, 겹치는 집합의 개수가 홀수이면 해당

rudalsd.tistory.com

 

먼저 모든 조합의 개수를 dp를 이용하여 구해줍니다. iCj = i-1Cj-1 + i-1Cj라는 점화식을 이용하여 구해주면 쉽게 구할 수 있습니다.

 

comb [ i ][ j ] = comb [ i - 1 ][ j - 1 ] + comb [ i - 1 ][ j ];

 

이를 통해서 포카드가 1개 이상일 때, 2개 이상일 때, 3개 이상일 때 ··· 13개 이상일 때의 조합의 개수를 각각 더해주거나 빼주면서 답을 구하면 됩니다.

 

포함 배제의 원리를 이용하여 포카드의 개수가 홀수일 때는 더해주고, 짝수일 때는 빼주면 답을 구할 수 있습니다.

 

[ 소스 코드 ]

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
#include <iostream>
 
#define MOD 10007
 
using namespace std;
 
int comb[53][53];
int N;
 
int main()
{
    for (int i = 0; i < 53; i++) {            //iCj의 조합을 dp를 활용해서 미리 구해 놓음
        for (int j = 0; j <= i; j++) {
            if (i == j || j == 0) {
                comb[i][j] = 1;
            }
            else if (j == 1) {
                comb[i][j] = i;
            }
            else {
                comb[i][j] = (comb[i - 1][j] + comb[i - 1][j - 1]) % MOD;
            }
        }
    }
 
    cin >> N;
    int ans = 0;
 
    for (int i = 1; i <= N / 4; i++) {    //포함 배제의 원리
        if (i % 2 == 1) {        //포카드 조합이 홀수일 때
            ans += (comb[13][i] * comb[52 - 4 * i][N - 4 * i]) % MOD;
        }
        else {                    //포카드 조합이 짝수일 때
            ans -= (comb[13][i] * comb[52 - 4 * i][N - 4 * i]) % MOD;
        }
        ans = (ans + MOD) % MOD;
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1019번 - 책 페이지 (C++)  (0) 2022.07.03
[ 백준 ] 17436번 - 소수의 배수 (C++)  (0) 2022.07.02
[ 백준 ] 15824번 - 너 봄에는 캡사이신이 맛있단다 (C++)  (0) 2022.06.30
[ 백준 ] 13334번 - 철로 (C++)  (0) 2022.06.29
[ 백준 ] 14725번 - 개미굴 (C++)  (0) 2022.06.28
반응형

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

 

15824번: 너 봄에는 캡사이신이 맛있단다

한 줄에 모든 조합의 주헌고통지수 합을 1,000,000,007로 나눈 나머지를 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제에서는 모듈러 연산이 필요하므로 다음 글을 읽고 오시면 좋습니다!

 

https://rudalsd.tistory.com/45?category=1064608 

 

[ 알고리즘 ] 모듈러 연산(Modular Arithmetic)

오늘은 모듈러 연산에 대해 설명드리겠습니다. 특정 수 M을 넘는 수에 모듈러 연산을 하려면 어떻게 해야 할까요? 모듈러 연산의 특성을 활용하면 쉽게 구할 수 있습니다. [ 동작 원리 ] 정수 A와

rudalsd.tistory.com

 

어떤 한 수가 조합 내에서 최댓값이 될 때의 개수와 최솟값이 될 때의 개수를 통해 쉽게 정답을 구할 수 있습니다.

 

먼저 입력받은 수를 오름차순으로 정렬한 후 for문을 돌면서 그 수가 최댓값이 될 때의 조합의 개수는 그 수보다 작은 수의 개수가 i일 때 2^i가 됩니다. 

 

마찬가지로 그 수가 최솟값이 될 때의 조합의 개수는 그 수보다 큰 수의 개수가 j일 때 2^j가 됩니다.

 

따라서 모든 수에 대해 (2^i - 2^j) * a를 구해서 더해주면 됩니다.

 

하지만 n의 최댓값이 300,000이므로 일반적인 방법으로는 2^300,000의 수를 구하기는 쉽지 않습니다. 따라서 분할 정복을 활용하여 답을 구해줍니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<algorithm>
#include<cstring>
 
#define MOD 1000000007
 
using namespace std;
 
int N;
long long arr[300001];
long long comb[300001];
long long ans;
 
long long Comb(int n)        //분할 정복을 통한 2의 n승 구하기
{
    if (comb[n] != -1) return comb[n];
    if (n % 2 == 0) {
        return comb[n] = ((Comb(n / 2) % MOD) * (Comb(n / 2) % MOD)) % MOD;
    }
    else {
        return comb[n] = ((Comb(n - 1) % MOD) * (Comb(1) % MOD)) % MOD;
    }
}
 
int main()
{
    cin >> N;
    memset(comb, -1, sizeof(comb));
    comb[0] = 1;
    comb[1] = 2;
 
    for (int i = 0; i < N; i++) {
        scanf("%lld", &arr[i]);
    }
 
    sort(arr, arr + N);
 
    for (int i = 0; i < N; i++) {        //arr[i]가 최대가 되는 조합의 개수에서 arr[i]가 최소가 되는 조합의 개수를 빼고
        ans += ((Comb(i) - Comb(N - i - 1) + MOD) % MOD) * (arr[i] % MOD);    //거기에 arr[i]를 곱한 것을 ans에 더함
        ans %= MOD;
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 17436번 - 소수의 배수 (C++)  (0) 2022.07.02
[ 백준 ] 16565번 - N포커 (C++)  (0) 2022.07.01
[ 백준 ] 13334번 - 철로 (C++)  (0) 2022.06.29
[ 백준 ] 14725번 - 개미굴 (C++)  (0) 2022.06.28
[ 백준 ] 2533번 - 사회망 서비스(SNS) (C++)  (0) 2022.06.27
반응형

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

 

12850번: 본대 산책2

가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

준영이가 정보관에서 1분 후 이동할 수 있는 건물은 전산관과 미래관입니다. 또한 전산관에서 1분 후 이동할 수 있는 건물은 신양관, 미래관 그리고 정보관입니다. 이를 행렬로 표현하면 다음과 같습니다.

 

그렇다면 각 건물에서 2분 후 이동할 수 있는 건물은 어떻게 구할 수 있을까요? 바로 1분 후 이동할 수 있는 건물들에 대한 행렬을 서로 곱하면 됩니다.

 

따라서 n분 후 이동할 수 있는 건물을 구하는 방법은 다음과 같습니다.

 

n % 2 == 0 일 때

mat( n / 2 ) * mat( n / 2 )

 

n % 2 == 1 일 때

mat( n - 1 ) * mat( 1 )

 

재귀를 통해 D번 이동했을 때 mat( D )의 0 , 0의 값을 출력하면 정보과학관으로 돌아오는 경우의 수를 구할 수 있습니다.

 

[ 소스 코드 ]

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <vector>
#include <unordered_map>
 
#define ll long long
 
using namespace std;
 
vector<vector<ll>> mat = {        //연결되어 있으면 1
    {0,1,1,0,0,0,0,0},
    {1,0,1,1,0,0,0,0},
    {1,1,0,1,1,0,0,0},
    {0,1,1,0,1,1,0,0},
    {0,0,1,1,0,1,1,0},
    {0,0,0,1,1,0,0,1},
    {0,0,0,0,1,0,0,1},
    {0,0,0,0,0,1,1,0}
};
 
int D;
ll MOD = 1000000007;
unordered_map<int, vector<vector<ll>>> m;
 
vector<vector<ll>> multi(vector<vector<ll>> A, vector<vector<ll>> B)    //A, B 행렬 곱
{
    vector<vector<ll>> ret;
    for (int i = 0; i < 8; i++) {
        vector<ll> tmp;
        for (int j = 0; j < 8; j++) {
            ll sum = 0;
            for (int k = 0; k < 8; k++) {
                sum += A[i][k] * B[k][j];
                sum %= MOD;
            }
            tmp.push_back( sum );
        }
        ret.push_back( tmp );
    }
 
    return ret;
}
 
vector<vector<ll>> dfs(int num)        //행렬을 num번 곱했을 때 배열
{
    if (m.find(num) != m.end()) {
        return m[num];
    }
    if (num % 2 == 0) {
        return m[num] = multi(dfs(num / 2), dfs(num / 2));
    }
    else {
        return m[num] = multi(dfs(num - 1), dfs(1));
    }
}
 
int main()
{
    cin >> D;
 
    m[1] = mat;
 
    dfs(D);
 
    cout<<m[D][0][0];
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 2568번 - 전깃줄 - 2 (C++)  (0) 2022.06.25
[ 백준 ] 14939번 - 불 끄기 (C++)  (0) 2022.06.24
[ 백준 ] 2098번 - 외판원 순회 (C++)  (0) 2022.06.22
[ 백준 ] 14003번 - 가장 긴 증가하는 부분 수열 5 (C++)  (0) 2022.06.21
[ 백준 ] 9328번 - 열쇠 (C++)  (0) 2022.06.20
반응형

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

 

2407번: 조합

n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

먼저 nCm의 값은 n-1Cm-1 + n-1Cm으로 표현할 수 있으므로 앞에서 구한 값을 더해서 자신의 값을 계산할 수 있습니다. 따라서 위와 같은 점화식을 사용해서 dp배열을 만들어 적용시켜 주었습니다. 

 

하지만 계산해야 할 수가 정수형으로 표현할 수 있는 값을 벗어나기에 숫자들을 string의 형태로 입력받고 string을 더해주는 함수를 따로 만든 후 각 숫자들을 더해주었습니다.

 

[ 소스 코드 ]

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <iostream>
#include <string>
 
using namespace std;
 
string dp[101][101];
 
string sum(string a, string b)                //a와 b를 더해주는 함수
{
    string ans = "";
 
    int lenA = a.size();
    int lenB = b.size();
    int len = max(lenA, lenB);
    int sum = 0;
    char num;
 
    while (lenB != len) {
        b = '0' + b;
        lenB++;
    }
    while (lenA != len) {
        a = '0' + a;
        lenA++;
    }
 
    for(int i=len - 1;i>=0;i--){
        sum = a[i] + b[i] - '0' - '0' + sum;
        num = sum % 10 + '0';
        ans = num + ans;
        sum /= 10;
    }
    if (sum != 0) {
        ans = (char)(sum + '0') + ans;
    }
 
 
    return ans;
}
 
string change(int num)                        //특정 int를 string의 형태로 바꿔주는 함수
{
    string ans = "";
    if (num > 99) {
        ans = "100";
    }
    else if(num > 9) {
        ans += (char)(num / 10 + '0');
        ans += (char)(num % 10 + '0');
    }
    else {
        ans = (char)(num + '0');
    }
 
    return ans;
}
 
int main()
{
    int n, m;
    cin >> n >> m;
 
    for (int i = 1; i <= 100; i++) {
        dp[i][1] = change(i);
    }
    
 
    for (int i = 2; i <= 100; i++) {
        for (int j = 2; j <= i; j++) {
            if (i == j) {                    //n과 m이 같을 때는 1이므로
                dp[i][j] = "1";
            }
            else {                            //아닐 때는 nCm = n-1Cm-1 + n-1Cm을 대입
                dp[i][j] = sum(dp[i - 1][j - 1], dp[i - 1][j]);
            }
        }
    }
 
    cout << dp[n][m];
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1562번 - 계단 수 (C++)  (0) 2022.05.29
[ 백준 ] 10844번 - 쉬운 계단 수 (C++)  (0) 2022.05.28
[ 백준 ] 1509번 - 팰린드롬 분할 (C++)  (0) 2022.05.26
[ 백준 ] 1208번 - 부분수열의 합 2 (C++)  (0) 2022.05.25
[ 백준 ] 17387번 - 선분 교차 2 (C++)  (0) 2022.05.24

+ Recent posts

티스토리툴바