수학

[devLupin]

지수법칙

---

• 밑이 같고 거듭제곱의 곱셈인 경우
  • 지수만 서로 더한다.
  • $a^2 a^3 a^4 =a^9$
• 거듭제곱의 거듭제곱
  • 지수만 서로 곱한다.
  • (a^m)^n = a^ (mn)

[devLupin]

모듈러 성질

---

• (a*b)%c = (a%c * b%c)%c

[devLupin]

모듈러 성질 BOJ 응용문제

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int a, b, c;

ll foo(ll y)
{
    if (y == 1) return a % c;
    ll val = foo(y / 2) % c;
    if (y % 2 == 0) return val*val%c;
    return val*val%c*a%c;
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> a >> b >> c;
    cout << foo(b);
    return 0;
}

[devLupin]

• 순열($nPr$)

  • n개의 카드 중에 r개를 뽑아 나열할 수 있는 경우의 수
  • 중복 가능

• 조합($nCr$)

  • n개의 카드 중에 r개를 뽑아 나열할 수 있는 경우의 수
  • 중복 불가능

• DFS, next_permutation으로 구현 가능

[devLupin]

조합($nCr$) via next_permutation

---

• bool 타입의 mask 배열 이용
• 처음 r개는 false, 이후 true로
  • fill()
• mask 배열의 false가 새로 뽑힌 조합이 된다.

const int N=15, R=5;
bool mask[N];

fill(mask + R, mask + N, true);
do {

} while(next_permutation(mask, mask+N);

[devLupin]

중복x, 조합 관련문제