let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

Codechef July 17 - Tree Expectancy

solution.md

Với \(n\) là số cạnh, công thức kì vọng cần tính là:

\[E = \frac{C^{n-1}_{2n-2}}{\frac{1}{n+1}C^n_{2n}} = \frac{n(n+1)}{4n-2}\]

Có thể xem chứng minh của công thức trong tài liệu ở trên.

Để tính nghịch đảo module, với \(b\) là số nguyên tố, ta có \(x^{-1} \equiv x^{b-2} \pmod{b}\)

main.cpp
Open in Github • Download 
#include <iostream>
#include <algorithm>
#include <vector>
#include <memory>
using namespace std;

#define LL long long

LL pow(LL a, LL n, LL m) {
    if (n == 0) return 1;
    LL t = pow(a, n>>1, m);
    if (n & 1) return t * t % m * a % m;
    return t * t % m;
}

LL calc(LL n, LL m) {
    n = n % m;
    LL r = n;
    r = (n + 1) % m * r % m;
    r = pow(4*n-2, m-2, m) * r % m;
    return r;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    while (T--) {
        LL n; cin >> n;
        n -= 1;
        cout << calc(n, 1000000007) << " " << calc(n, 1000000009) << '\n';
    }
}
Comments