Thắc mắc của Mitrut - LCOJ: Luyện Code Online Judge

ARBORE - Thắc mắc của Mitrut

Điểm: 3,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hiếu Nguyễn

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Mitrut có số tự nhiên ~N~ và một cây có ~N~ đỉnh. Cậu thắc mắc rằng có bao nhiêu cách để đặt ~N~ số khác nhau vào cây, mỗi số trên một nút thỏa mản rằng số ở nút ~A~ nhỏ hơn số của tất cả các nút là con của ~A~. Gốc của cây luôn là nút ~1~.

Do kết quả có thể rất lớn nên bạn chỉ cần tìm số dư khi chia kết quả tìm được với ~666013~.

Input

Dòng đầu tiên ghi số ~N\ (1 ≤N ≤ 100000)~;
~N-1~ dòng tiếp theo, mỗi dòng ghi hai số nguyên ~x~ và ~y~, thể hiện có một cạnh nối giữa hai đỉnh ~x~ và ~y\ (x ≠y,1 ≤ x ≤ N , 1 ≤ y ≤ N)~.

Giới hạn:

~70\%~ số test có ~N ≤ 2000~;
~10\%~ số test có ~N ≤ 7~.

Output

Ghi ra một số nguyên duy nhất là kết quả cần tính.

Sample

Input #1

Output #1

Hint

Với bộ test trên, các cách để đánh số là:

Problem source: Kc97ble - Free Contest

Bình luận

Please read the guidelines before commenting.

có công thức tính

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

const int mod = 666013;
int size_v[1000001];
bool vis[1000001];
int powmod(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = (res * 1LL * a) % mod;
        a = (a * 1LL * a) % mod;
        b >>= 1;
    }
    return res;
}
void dfs(int node, vector<vector<int>>& adj) {
    vis[node] = true;
    size_v[node] = 1;
    for (auto& child : adj[node]) {
        if (!vis[child]) {
            dfs(child, adj);
            size_v[node] += size_v[child];
        }
    }   
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n; cin >> n;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }   
    dfs(1, adj);
    int fact = 1;
    for(int i = 1; i <= n; i++) fact = (fact * 1LL * i) % mod;
    int prod = 1;
    for (int i = 1; i <= n; i++) {
        prod = (prod * 1LL * size_v[i]) % mod;
    }
    cout << (fact * 1LL * powmod(prod, mod - 2)) % mod << "\n";
}

1
phatdu12345 đã bình luận lúc 1, Tháng 2, 2024, 17:14
Gợi í cách làm của tui:

Đếm có bao nhiêu hàng có số 1 và đó sẽ là giá trị của biến 'nexttoroot'

Lọc phần tử phân biệt để LẤY SỐ PHẦN TỬ và số phần tử đó = biến 'n' --> dùng set để lọc số phần tử phân biệt

Cuối cùng, Đáp án = (nexttoroot * (n - 2)!) % 666013