Pagini recente » Cod sursa (job #1620913) | Cod sursa (job #3345658) | Cod sursa (job #2852427) | Cod sursa (job #1637047) | Cod sursa (job #3356805)
#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;
}