Submission #1336590

#	Time	Username	Problem	Language	Result	Execution time	Memory
1336590		sh_qaxxorov_571	Struktura (COCI26_struktura)	C++20	Compilation error	0 ms	0 KiB

Main

#include <iostream>

using namespace std;

long long MOD = 1e9 + 7;

// Darajaga ko'tarish funksiyasi (Modular Exponentiation)
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// Modular teskari sonni topish (Fermat's Little Theorem)
long long modInverse(long long n) {
    return power(n, MOD - 2);
}

// Fibonachchi sonini O(log N) vaqtda topish uchun matritsa ko'paytirish
struct Matrix {
    long long mat[2][2];
    Matrix() {
        mat[0][0] = mat[0][1] = mat[1][0] = mat[1][1] = 0;
    }
};

Matrix multiply(Matrix A, Matrix B) {
    Matrix C;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                C.mat[i][j] = (C.mat[i][j] + A.mat[i][k] * B.mat[k][j]) % MOD;
    return C;
}

Matrix matrix_power(Matrix A, long long p) {
    Matrix res;
    res.mat[0][0] = 1; res.mat[1][1] = 1;
    while (p > 0) {
        if (p & 1) res = multiply(res, A);
        A = multiply(A, A);
        p >>= 1;
    }
    return res;
}

int main() {
    long long n, k;
    if (!(cin >> n >> k)) return 0; [cite: 17]

    // Agar k < n bo'lsa, 1 dan n gacha sonlarni ishlatib bo'lmaydi
    if (k < n) {
        cout << 0 << endl; 
        return 0;
    }

    // Shartga mos permutatsiyalar soni F_n ni hisoblaymiz
    // F_1 = 1, F_2 = 2, F_3 = 3...
    Matrix T;
    T.mat[0][0] = 1; T.mat[0][1] = 1;
    T.mat[1][0] = 1; T.mat[1][1] = 0;
    
    T = matrix_power(T, n);
    long long Fn = T.mat[0][0]; // n-chi Fibonachchi soni (permutatsiyalar soni)

    // Umumiy holatlar soni: k^n
    long long total_outcomes = power(k, n);

    // Ehtimollik: Fn / k^n
    long long ans = (Fn * modInverse(total_outcomes)) % MOD; 

    cout << ans << endl; 

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:54:38: error: 'cite' was not declared in this scope
   54 |     if (!(cin >> n >> k)) return 0; [cite: 17]
      |                                      ^~~~
Main.cpp:54:42: error: expected ',' before ':' token
   54 |     if (!(cin >> n >> k)) return 0; [cite: 17]
      |                                          ^
      |                                          ,
Main.cpp:54:42: error: expected identifier before ':' token
Main.cpp: In lambda function:
Main.cpp:57:5: error: expected '{' before 'if'
   57 |     if (k < n) {
      |     ^~
Main.cpp: In function 'int main()':
Main.cpp:54:47: error: expected ';' before 'if'
   54 |     if (!(cin >> n >> k)) return 0; [cite: 17]
      |                                               ^
      |                                               ;
......
   57 |     if (k < n) {
      |     ~~