14. 누적 합

14.md

0.00MB

0. 복습
1. 누적합 or 부분합 or Prefix Sum or Partial Sum

11659문제를 보면, 입력이 주어질 때 마다 합을 구해서 출력하면, O(MN)으로 시간초과가 뜨게 된다.

이 문제는 미리 합을 구해 놓고 질문이 들어올 때마다 값을 출력해야 한다.

S[i] : 1~i까지의 합이라고 정의하고,

S[i] = S[i-1] + A[i]의 식을 사용한다.

L~R까지의 합은 S[R] - S[L-1]으로 구할 수 있으며, 이는 O(1)의 시간복잡도를 가지게 된다.

#include <iostream>
using namespace std;
int dp[100001];
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    int N, M; cin >> N >> M;
    for(int i=1; i<=N; ++i){
        int a; cin >> a;
        dp[i] = dp[i-1]+a;
    }
    while(M--){
        int a, b;
        cin >> a >> b;
        cout << dp[b]-dp[a-1] << '\n';
    }
}

누적 합은 역원이 있어야 사용할 수 있는 방법이다.

16713번은 특정 구간의 XOR값을 출력해야 한다.

L~R까지의 합은 dp[R]-dp[L-1]으로 구할 수 있다. +의 역원은 -이기 때문에 가능한 것이다.

L~R까지의 곱은 dp[R]/dp[L-1]으로 구할 수 있다. *의 역원은 /이기 때문에 가능한 것이다.

L~R까지의 XOR은 dp[R]^dp[L-1]으로 구할 수 있다. ^의 역원은 ^이기 때문에 가능한 것이다.

참고 문제 : 11659, 11441, 17390, 16713, 16139, 11660, 10986

2. 거듭제곱의 나머지

a의 b제곱을 C로 나눈 나머지를 구하고 싶다.

a, b, C의 제한이 21억일 때, 어떻게 해야할까? 1629번을 보자.

a의 n승은 짝수일 때 (a의 n/2승)의 2승, 또는 홀수일 때 (a의 n-1승) * n으로 쓸 수 있다.

즉 b가 28일 때, 28 -> 14 -> 7 -> 6 -> 3 -> 2 -> 1 -> 0 해서 O(logN)만에 끝낼 수 있다.

한가지 방법이 더 있다. 13171번에 친절히 설명되어있다.

참고 : 1629, 13171

3. 행렬의 제곱

위의 방법에서 조금 발전해서, 단순 자연수끼리 계산이 아닌, 행렬끼리 계산도 수행할 수 있다.

행렬 구현 및 행렬 곱셈 계산 방법을 알고 있다면 쉽게 해결할 수 있다.

10830번을 이렇게 해결 할 수 있다. 함정은 입력에서 1000이 주어질 수 있어서 이것도 나머지를 해주어야 한다.

#include <iostream>
#include <vector>

#define ll long long
#define mat vector<vector<ll> > // 메트릭스
using namespace std;
const ll M = 1000;
int N;
ll B;
mat mul(mat a, mat b){
    mat c(a.size(), vector<ll>(b[0].size(), 0)); // 초기화
    for(int i=0; i<a.size(); ++i){
        for(int j=0; j<b[0].size(); ++j){
            for(int k=0; k<b.size(); ++k){
                c[i][j] += a[i][k] * b[k][j];
                c[i][j] %= M;
            }
        }
    }
    return c;
}
mat pw(mat a, ll n){
    if(n==1){
        return a;
    }
    if(n%2) return mul(pw(a, n-1), a);
    mat tmp = pw(a, n/2);
    return mul(tmp, tmp);
}
int main(){
    cin >> N >> B;
    mat A(N, vector<ll>(N, 0));
    for(int i=0; i<N; ++i){
        for(int j=0; j<N; ++j){
            cin >> A[i][j];
            A[i][j] %= M;
        }
    }
    A = pw(A, B);
    for(int i=0; i<N; ++i){
        for(int j=0; j<N; ++j){
            cout << A[i][j] << " ";
        }
        cout << '\n';
    }
}

vector 쓰는게 어렵다면, struct를 사용할 수도 있다.

#include <iostream>
#include <vector>

#define ll long long
struct m {
    ll arr[5][5];
};
using namespace std;
const ll M = 1000;
int N;
ll B;
m mmul(m a, m b){
    m c;
    for(int i=0; i<N; ++i){
        for(int j=0; j<N; ++j){
            c.arr[i][j] = 0;
            for(int k=0; k<N; ++k){
                c.arr[i][j]+=a.arr[i][k] * b.arr[k][j];
                c.arr[i][j]%=M;
            }
        }
    }
    return c;
}
m mpw(m a, ll n){
    if(n==1) return a;
    if(n%2) return mmul(mpw(a, n-1), a);
    m mtmp = mpw(a, n/2);
    return mmul(mtmp, mtmp);
}
int main(){
    cin >> N >> B;
    m A;
    for(int i=0; i<N; ++i){
        for(int j=0; j<N; ++j){
            cin >> A.arr[i][j];
            A.arr[i][j]%=M;
        }
    }
    A = mpw(A, B);
    for(int i=0; i<N; ++i){
        for(int j=0; j<N; ++j){
            cout << A.arr[i][j] << " ";
        }
        cout << '\n';
    }
}

자. 2749번을 보자.

1 1
1 0 행렬에

f1
f0 행렬을 곱하면

f0+f1
f1 이렇게 행렬이 나온다. 여기서 f0+f1=f2이므로

1 1
1 0행렬을 n-1번 곱하면 n번째 피보나치 수가 나온다.

참고 : 10830, 2749, 11444, 14440