Cod sursa(job #3356805)

Utilizator Dumitru_SerbinaDumitru Serbina Dumitru_Serbina Data 4 iunie 2026 12:33:57
Problema Ridicare la putere in timp logaritmic Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 3.31 kb
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define MOD_PRIME 30103

typedef struct {
    int  n_val;
    int  s_val;
    int* fact;     
    int* invFact;  
} FuncEngine;

int power_mod(int base, int exp) {
    int64_t result = 1;
    int64_t current_base = base % MOD_PRIME;
    
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * current_base) % MOD_PRIME;
        }
        current_base = (current_base * current_base) % MOD_PRIME;
        exp /= 2;
    }
    return (int)result;
}

FuncEngine* init_funcEngine(int n, int s) {
    FuncEngine* engine = (FuncEngine*)malloc(sizeof(FuncEngine));
    if (engine == NULL) {
        perror(NULL);
        exit(1);
    }

    engine->n_val = n;
    engine->s_val = s;

    engine->fact = (int*)malloc(sizeof(int) * MOD_PRIME);
    if (engine->fact == NULL) {
        perror(NULL);
        free(engine);
        exit(1);
    }

    engine->invFact = (int*)malloc(sizeof(int) * MOD_PRIME);
    if (engine->invFact == NULL) {
        perror(NULL);
        free(engine->fact);
        free(engine);
        exit(1);
    }

    engine->fact[0] = 1;
    for (int i = 1; i < MOD_PRIME; i++) {
        int64_t step_calc = (int64_t)engine->fact[i - 1] * i;
        engine->fact[i] = (int)(step_calc % MOD_PRIME);
    }

    engine->invFact[MOD_PRIME - 1] = power_mod(engine->fact[MOD_PRIME - 1], MOD_PRIME - 2);
    for (int i = MOD_PRIME - 2; i >= 0; i--) {
        int64_t step_calc = (int64_t)engine->invFact[i + 1] * (i + 1);
        engine->invFact[i] = (int)(step_calc % MOD_PRIME);
    }

    return engine;
}

void free_funcEngine(FuncEngine* engine) {
    if (engine != NULL) {
        free(engine->fact);
        free(engine->invFact);
        free(engine);
    }
}

int compute_comb_small(FuncEngine* engine, int n, int k) {
    if (k < 0 || k > n) {
        return 0;
    }
    int64_t low_level_calc = ((int64_t)engine->fact[n] * engine->invFact[k]) % MOD_PRIME;
    return (int)((low_level_calc * engine->invFact[n - k]) % MOD_PRIME);
}

int compute_lucas(FuncEngine* engine, int n, int k) {
    int64_t total_combinations = 1;
    
    while (n > 0 || k > 0) {
        int ni = n % MOD_PRIME;
        int ki = k % MOD_PRIME;
        
        int small_comb = compute_comb_small(engine, ni, ki);
        total_combinations = (total_combinations * small_comb) % MOD_PRIME;
        
        n /= MOD_PRIME;
        k /= MOD_PRIME;
    }
    
    return (int)total_combinations;
}

int solve_functii(FuncEngine* engine) {
    int n = engine->n_val;
    int s = engine->s_val;

    if (n > s) {
        return 0;
    }
    if (n == 1) {
        return s % MOD_PRIME;
    }

    int combinations = compute_lucas(engine, s, n);
    
    int64_t final_answer = (2 * (int64_t)combinations) % MOD_PRIME;
    return (int)final_answer;
}

int main(void) {
    FILE* fin = fopen("functii.in", "r");
    if (fin == NULL) {
        perror(NULL);
        exit(1);
    }

    FILE* fout = fopen("functii.out", "w");
    if (fout == NULL) {
        perror(NULL);
        fclose(fin);
        exit(1);
    }

    int n, s;
    if (fscanf(fin, "%d %d", &n, &s) == 2) {
        FuncEngine* engine = init_funcEngine(n, s);
        
        int result = solve_functii(engine);
        fprintf(fout, "%d\n", result);
        
        free_funcEngine(engine);
    }

    fclose(fin);
    fclose(fout);
    return 0;
}