boj 11505 - 구간 곱 구하기

목차

문제 풀이

코드 보기

---

문제 풀이

구간 합 구하기의 응용 버전입니다. Segment tree에 관한 설명은 다음 게시글을 참조하면 됩니다.

 세그먼트 트리, BOJ2042

 

BOJ 2042에서는 각 노드에 구간 합을 저장했다면 이번에는 구간 곱을 저장하면 됩니다.

 

※ Check List!

매 계산할 때마다 1,000,000,007로 나눠야 합니다.

더하기와는 다르게 어떤 수 a와 b를 곱할 때 1,000,000,007 보다 작은 수를 곱하게 되겠죠. 그런데 이 값은 Integer를 초과합니다. 따라서 중간 과정은 모두 long type이어야 합니다.

 

 

빨간색으로 칠해진 node는 모두 1,000,000,007을 넘겨 modular 연산된 숫자들입니다.

 

만약, 저기서 modular연산을 해주지 않았다고 생각해 봅시다!

 

1,695,935,039,236,263,572,947,200,000라는 어마무시한 숫자가 1번 node에 저장될 텐데 이는 9,223,372,036,854,775,807 (8byte unsigned 한계)를 훌쩍 넘어갑니다.

 

 

$ (a * b)\%c = (a\%c * b\%c)\%c $ 식이 성립하지만, 이미 a 혹은 b가 overflow가 발생한 숫자라면 성립되지 않습니다. 따라서 미리미리 modular연산을 해 놓아야 합니다!

---

코드 보기

BOJ2042, 구간 곱 구하기

 

기존의 구간 합 구하기와 코드가 별 반 차이가 없습니다! 다만,

1. 맨 위에 매크로로 MOD를 1,000,000,007로 정의해 두자!
2. 곱하기 연산을 할 때마다 % MOD 연산을 수행해 주자!

이 둘을 유념해 두시면 되겠습니다.

#include<stdio.h>
#define MOD 1000000007

typedef long long int LLI;

class Tree{
        public:
        LLI node[2048576*2];

        //Init
        LLI Init(int cur, LLI* arr, int left, int right){
                if(left==right){
                        node[cur] = arr[left];
                        return node[cur];
                }
                int mid = (left+right)/2;
                return node[cur] = (Init(cur*2, arr, left, mid) * Init(cur*2+1,arr, mid+1, right))%MOD;
        }

        //Search
        LLI Search(int cur, int left, int right, int start, int end){
                if(left<=start && right>=end) return node[cur];
                int mid = (start+end)/2;
                LLI sum = 1;
                if(left<=mid) sum *= Search(cur*2, left, right, start, mid);
                if(right>mid) sum = (sum * Search(cur*2+1, left, right, mid+1, end))%MOD;
                return sum;
        }
        Tree(){

        }

        //Update
        void Update(int cur, int index, LLI val, int left, int right){
                if(left==right){
                        node[cur] = val;
                        return;
                }
                int mid = (left+right)/2;
                if(index <= mid) Update(cur*2, index, val, left, mid);
                if(index > mid) Update(cur*2+1, index, val, mid+1, right);
                node[cur] = (node[cur*2] * node[cur*2+1])%MOD;
        }
};

int N,M,K;
LLI arr[1000000];
int main(){
        scanf("%d %d %d",&N,&M,&K);
        Tree* t = new Tree();
        for(int i=0 ; i<N ; i++){
                scanf("%lld",&arr[i]);
        }
        t->Init(1, arr, 0, N-1);

        int query;
        LLI a, b;
        for(int i=0 ; i<M+K ; i++){
                scanf("%d %lld %lld",&query, &a,&b);
                a--;
                if(query==1){
                        t->Update(1, a, b, 0, N-1);
                }else if(query==2){
                        b--;
                        printf("%lld\n",t->Search(1, a, b, 0, N-1));
                }
        }
        return 0;
}