본문 바로가기
분할 정복을 이용한 거듭제곱/다항식 거듭제곱

Kitamasa 정답 코드 모음

song seong min 2023. 9. 16. 23:03

복잡도 - 제목1

문제번호 - 속도

선형점화식 문제 중 행렬 곱으로도 통과하지만, kitamasa법을 사용했을 때 실행속도에서 이득을 본 문제들입니다.

O(N^2)

백준 17272 - 8ms

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define mod 1000000007

typedef long long element;
typedef element* poly; // polynomial = sum poly[i] * x^i

poly multiply_polynomial(poly A, int degree_A, poly B, int degree_B);
poly remainder_polynomial(poly A, int degree_A, poly B, int degree_B, int* degree_result);
poly power_polynomial_modular (poly A, int degree_A, long long P, poly B, int degree_B, int* degree_result);

long long find_nth_term_modular (long long N, long long coefficient[], long long initial[], int size_recurrence);

int main() {
    
    long long N, M;
    scanf("%lld %lld", &N, &M);
    
    int size_recurrence = M;
    long long coef[101] = {};
    coef[1] = 1;
    coef[M] = 1;
    
    long long init[100] = {};
    for (int i = 0; i < M; i++) {
        init[i] = 1;
    }
    
    printf("%lld", find_nth_term_modular(N, coef, init, size_recurrence));
    
    return 0;
}

poly multiply_polynomial(poly A, int degree_A, poly B, int degree_B) {
    // R = A * B
    int degree_R = degree_A + degree_B;
    poly R = calloc(degree_R + 1, sizeof(element));
    for (int i = 0; i <= degree_A; i++) {
        for (int j = 0; j <= degree_B; j++) {
            R[i+j] = (R[i+j] + A[i] * B[j]) % mod;
        }
    }
    return R;
}

poly remainder_polynomial(poly A, int degree_A, poly B, int degree_B, int* degree_result) {
    // A = Q * B + R
    if (degree_A < degree_B) {
        *degree_result = degree_A;
        return A;
    }
    // degree_A >= degree_B is guaranteed
    poly T = calloc(degree_A + 1, sizeof(element));
    memcpy(T, A, (degree_A + 1) * sizeof(element)); // T := A
   
    // degree_Q == degree_A - degree_B
    poly Q = calloc(degree_A - degree_B + 1, sizeof(element));
	for (int i = degree_A - degree_B; i >= 0; i--) {
		Q[i] = T[i + degree_B] / B[degree_B]; // calculate coefficient of x^i in Q
		for (int j = 0; j <= degree_B; j++) {
		    T[i + j] = (T[i+j] + mod - Q[i] * B[j] % mod) % mod; // A -= Q * B
	    }
	}
	
	poly R = calloc(degree_B + 1, sizeof(element));
	memcpy(R, T, (degree_B + 1) * sizeof(element));
	*degree_result = degree_B;
	
	return R;
}

poly power_polynomial_modular (poly A, int degree_A, long long P, poly B, int degree_B, int* degree_result) {
    int degree_R = 0;
    poly R = calloc(degree_R + 1, sizeof(element));
    R[0] = 1;
   
    while(P) {
        if (P % 2) {
            R = multiply_polynomial(R, degree_R, A, degree_A);
            degree_R += degree_A;
           
            R = remainder_polynomial(R, degree_R, B, degree_B, &degree_R);
        }
        A = multiply_polynomial(A, degree_A, A, degree_A);
        degree_A *= 2;
       
        A = remainder_polynomial(A, degree_A, B, degree_B, &degree_A);
       
        P /= 2;
    }
    *degree_result = degree_R;
    return R;
}

long long find_nth_term_modular (long long N, long long coefficient[], long long initial[], int size_recurrence) {
    if (N < size_recurrence) {
        return initial[N];
    }
    
    int degree_F = size_recurrence;
    poly F = calloc(degree_F + 1, sizeof(element));
    for (int i = 0; i < size_recurrence; i++) {
        F[i] = mod - coefficient[size_recurrence - i];
    }
    F[degree_F] = 1;
    
    int degree_A = 1;
    poly A = calloc(degree_A + 1, sizeof(element));
    A[1] = 1;
    
    int degree_D;
    poly D = power_polynomial_modular(A, degree_A, N, F, degree_F, &degree_D);
    
    long long result = 0;
    for (int i = 0; i <= degree_D; i++) {
        result = (result + D[i] * initial[i]) % mod;
    }
    return result;
}

점화식 - 추가 예정

초기 항 - 추가 예정

백준 23819 - 12ms

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long long mod;

typedef long long element;
typedef element* poly; // polynomial = sum poly[i] * x^i

poly multiply_polynomial(poly A, int degree_A, poly B, int degree_B);
poly remainder_polynomial(poly A, int degree_A, poly B, int degree_B, int* degree_result);
poly power_polynomial_modular (poly A, int degree_A, long long P, poly B, int degree_B, int* degree_result);

long long find_nth_term_modular (long long N, long long coefficient[], long long initial[], int size_recurrence);

int main() {
    
    long long N, K;
    scanf("%lld %lld", &N, &K);
    
    int size_recurrence = K;
    long long coef[101] = {};
    for (int i = 1; i <= K; i++) {
        coef[i] = 1;
    }
    
    long long init[100] = {};
    long long sum = 0;
    for (int i = 1; i < K; i++) {
        scanf("%lld", &init[i]);
        sum += init[i];
    }
    long long a_k;
    scanf("%lld", &a_k);
    
    scanf("%lld", &mod);
    sum %= mod;
    init[0] = (a_k + mod - sum) % mod;
    
    printf("%lld", find_nth_term_modular(N, coef, init, size_recurrence));
    
    return 0;
}

poly multiply_polynomial(poly A, int degree_A, poly B, int degree_B) {
    // R = A * B
    int degree_R = degree_A + degree_B;
    poly R = calloc(degree_R + 1, sizeof(element));
    for (int i = 0; i <= degree_A; i++) {
        for (int j = 0; j <= degree_B; j++) {
            R[i+j] = (R[i+j] + A[i] * B[j]) % mod;
        }
    }
    return R;
}

poly remainder_polynomial(poly A, int degree_A, poly B, int degree_B, int* degree_result) {
    // A = Q * B + R
    if (degree_A < degree_B) {
        *degree_result = degree_A;
        return A;
    }
    // degree_A >= degree_B is guaranteed
    poly T = calloc(degree_A + 1, sizeof(element));
    memcpy(T, A, (degree_A + 1) * sizeof(element)); // T := A
   
    // degree_Q == degree_A - degree_B
    poly Q = calloc(degree_A - degree_B + 1, sizeof(element));
	for (int i = degree_A - degree_B; i >= 0; i--) {
		Q[i] = T[i + degree_B] / B[degree_B]; // calculate coefficient of x^i in Q
		for (int j = 0; j <= degree_B; j++) {
		    T[i + j] = (T[i+j] + mod - Q[i] * B[j] % mod) % mod; // A -= Q * B
	    }
	}
	
	poly R = calloc(degree_B + 1, sizeof(element));
	memcpy(R, T, (degree_B + 1) * sizeof(element));
	*degree_result = degree_B;
	
	return R;
}

poly power_polynomial_modular (poly A, int degree_A, long long P, poly B, int degree_B, int* degree_result) {
    int degree_R = 0;
    poly R = calloc(degree_R + 1, sizeof(element));
    R[0] = 1;
   
    while(P) {
        if (P % 2) {
            R = multiply_polynomial(R, degree_R, A, degree_A);
            degree_R += degree_A;
           
            R = remainder_polynomial(R, degree_R, B, degree_B, &degree_R);
        }
        A = multiply_polynomial(A, degree_A, A, degree_A);
        degree_A *= 2;
       
        A = remainder_polynomial(A, degree_A, B, degree_B, &degree_A);
       
        P /= 2;
    }
    *degree_result = degree_R;
    return R;
}

long long find_nth_term_modular (long long N, long long coefficient[], long long initial[], int size_recurrence) {
    if (N < size_recurrence) {
        return initial[N];
    }
    
    int degree_F = size_recurrence;
    poly F = calloc(degree_F + 1, sizeof(element));
    for (int i = 0; i < size_recurrence; i++) {
        F[i] = mod - coefficient[size_recurrence - i];
    }
    F[degree_F] = 1;
    
    int degree_A = 1;
    poly A = calloc(degree_A + 1, sizeof(element));
    A[1] = 1;
    
    int degree_D;
    poly D = power_polynomial_modular(A, degree_A, N, F, degree_F, &degree_D);
    
    long long result = 0;
    for (int i = 0; i <= degree_D; i++) {
        result = (result + D[i] * initial[i]) % mod;
    }
    return result;
}

점화식 - 추가 예정

초기 항 - 추가 예정

백준 6673 - 4ms

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define mod 10000

typedef long long element;
typedef element* poly; // polynomial = sum poly[i] * x^i

poly multiply_polynomial(poly A, int degree_A, poly B, int degree_B);
poly remainder_polynomial(poly A, int degree_A, poly B, int degree_B, int* degree_result);
poly power_polynomial_modular (poly A, int degree_A, long long P, poly B, int degree_B, int* degree_result);

long long find_nth_term_modular (long long N, long long coefficient[], long long initial[], int size_recurrence);

int main() {
    
    while(1) {
        long long K;
        scanf("%lld", &K);
        if (K == 0) return 0;
        
        int size_recurrence = K;
        long long init[100] = {};
        for (int i = 0; i < K; i++) {
            scanf("%lld", &init[i]);
        }
        
        long long coef[101] = {};
        for (int i = 1; i <= K; i++) {
            scanf("%lld", &coef[i]);
        }
        
        long long N;
        scanf("%lld", &N);
        
        printf("%lld\n", find_nth_term_modular(N, coef, init, size_recurrence));
    }
    return 0;
}

poly multiply_polynomial(poly A, int degree_A, poly B, int degree_B) {
    // R = A * B
    int degree_R = degree_A + degree_B;
    poly R = calloc(degree_R + 1, sizeof(element));
    for (int i = 0; i <= degree_A; i++) {
        for (int j = 0; j <= degree_B; j++) {
            R[i+j] = (R[i+j] + A[i] * B[j]) % mod;
        }
    }
    return R;
}

poly remainder_polynomial(poly A, int degree_A, poly B, int degree_B, int* degree_result) {
    // A = Q * B + R
    if (degree_A < degree_B) {
        *degree_result = degree_A;
        return A;
    }
    // degree_A >= degree_B is guaranteed
    poly T = calloc(degree_A + 1, sizeof(element));
    memcpy(T, A, (degree_A + 1) * sizeof(element)); // T := A
   
    // degree_Q == degree_A - degree_B
    poly Q = calloc(degree_A - degree_B + 1, sizeof(element));
	for (int i = degree_A - degree_B; i >= 0; i--) {
		Q[i] = T[i + degree_B] / B[degree_B]; // calculate coefficient of x^i in Q
		for (int j = 0; j <= degree_B; j++) {
		    T[i + j] = (T[i+j] + mod - Q[i] * B[j] % mod) % mod; // A -= Q * B
	    }
	}
	
	poly R = calloc(degree_B + 1, sizeof(element));
	memcpy(R, T, (degree_B + 1) * sizeof(element));
	*degree_result = degree_B;
	
	return R;
}

poly power_polynomial_modular (poly A, int degree_A, long long P, poly B, int degree_B, int* degree_result) {
    int degree_R = 0;
    poly R = calloc(degree_R + 1, sizeof(element));
    R[0] = 1;
   
    while(P) {
        if (P % 2) {
            R = multiply_polynomial(R, degree_R, A, degree_A);
            degree_R += degree_A;
           
            R = remainder_polynomial(R, degree_R, B, degree_B, &degree_R);
        }
        A = multiply_polynomial(A, degree_A, A, degree_A);
        degree_A *= 2;
       
        A = remainder_polynomial(A, degree_A, B, degree_B, &degree_A);
       
        P /= 2;
    }
    *degree_result = degree_R;
    return R;
}

long long find_nth_term_modular (long long N, long long coefficient[], long long initial[], int size_recurrence) {
    if (N < size_recurrence) {
        return initial[N];
    }
    
    int degree_F = size_recurrence;
    poly F = calloc(degree_F + 1, sizeof(element));
    for (int i = 0; i < size_recurrence; i++) {
        F[i] = mod - coefficient[size_recurrence - i];
    }
    F[degree_F] = 1;
    
    int degree_A = 1;
    poly A = calloc(degree_A + 1, sizeof(element));
    A[1] = 1;
    
    int degree_D;
    poly D = power_polynomial_modular(A, degree_A, N, F, degree_F, &degree_D);
    
    long long result = 0;
    for (int i = 0; i <= degree_D; i++) {
        result = (result + D[i] * initial[i]) % mod;
    }
    return result;
}

점화식 - 추가 예정

초기항 - 추가 예정

 

'분할 정복을 이용한 거듭제곱 > 다항식 거듭제곱' 카테고리의 다른 글

백준 10961번: School canteen (Kitamasa)  (0) 2023.09.24
백준 27308번: 창호의 유학 준비  (0) 2023.09.19

'분할 정복을 이용한 거듭제곱/다항식 거듭제곱' Related Articles

티스토리툴바