Submission #6016080


Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) x
#define WATCH(x) TRACE(cout << #x" = " << x << endl)
#define WATCHR(a, b) TRACE(for (auto it=a; it!=b;) cout << *(it++) << " "; cout << endl)
#define WATCHC(V) TRACE({cout << #V" = "; WATCHR(V.begin(), V.end());})

#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vs = vector<string>;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<int MOD> struct modnum {
    int v;
    modnum() : v(0) {}
    modnum(ll _v) : v(_v % MOD) { if (v < 0) v += MOD; }
    explicit operator int() const { return v; }
    friend istream& operator >> (istream& i, modnum& n) { ll v; i >> v; n = modnum(v); return i; }
    friend ostream& operator << (ostream& o, const modnum& n) { return o << n.v; }

    friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
    friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }

    modnum& operator += (const modnum& o) { v += o.v; if (v >= MOD) v -= MOD; return *this; }
    modnum& operator -= (const modnum& o) { v -= o.v; if (v < 0) v += MOD; return *this; }
    modnum& operator *= (const modnum& o) { v = int(ll(v) * ll(o.v) % MOD); return *this; }
    modnum operator - () { modnum res; if (v) res.v = MOD - v; return res; }
    friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
    friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
    friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }

    modnum pow(ll e) const {
        if (e == 0) return 1;
        if (e & 1) return *this * this->pow(e-1);
        return (*this * *this).pow(e/2);
    }

    modnum inv() const {
        int g = MOD, x = 0, y = 1;
        for (int r = v; r != 0; ) {
            int q = g / r;
            g %= r; swap(g, r);
            x -= q * y; swap(x, y);
        }

        assert(g == 1);
        assert(y == MOD || y == -MOD);
        return x < 0 ? x + MOD : x;
    }
    modnum& operator /= (const modnum& o) { return (*this) *= o.inv(); }
    friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= modnum(b); }

    static int totient() {
        int tot = MOD, tmp = MOD;
        for (int p = 2; p * p <= tmp; p++) if (tmp % p == 0) {
            tot = tot / p * (p - 1);
            while (tmp % p == 0) tmp /= p;
        }
        if (tmp > 1) tot = tot / tmp * (tmp - 1);
        return tot;
    }

    static int primitive_root() {
        if (MOD == 1) return 0;
        if (MOD == 2) return 1;

        int tot = totient(), tmp = tot;
        vi tot_pr;
        for (int p = 2; p * p <= tmp; p++) if (tot % p == 0) {
            tot_pr.push_back(p);
            while (tmp % p == 0) tmp /= p;
        }
        if (tmp > 1) tot_pr.push_back(tmp);

        for (int r = 2; r < MOD; r++) if (__gcd(r, MOD) == 1) {
            bool root = true;
            for (int p : tot_pr) root &= modnum(r).pow(tot / p) != 1;
            if (root) return r;
        }
        assert(false);
    }

    static modnum generator() { static modnum g = primitive_root(); return g; }
    static int discrete_log(modnum v) {
        static const int M = ceil(sqrt(MOD));
        static unordered_map<int, int> table;
        if (table.empty()) {
            modnum e = 1;
            for (int i = 0; i < M; i++) { table[e.v] = i; e *= generator(); }
        }
        static modnum f = generator().pow(totient() - M);

        for (int i = 0; i < M; i++) {
            if (table.count(v.v)) return table[v.v] + i * M;
            v *= f;
        }
        assert(false);
    }

    static modnum fact(int n) {
        static vector<modnum<MOD>> fact = { 1 };
        while (fact.size() <= n)
            fact.push_back(fact.back() * fact.size());
        return fact[n];
    }

    static modnum ncr(int n, int r) {
        if (r < 0 || n < r) return 0;
        return fact(n) / (fact(r) * fact(n - r));
    }
};
using mn = modnum<int(1e9 + 7)>;
using vmn = vector<mn>;
using vvmn = vector<vmn>;

int centroid(vvi& adj, vi& subt, int loc, int par) {
    int ret = -1;
    bool bad = false;
    subt[loc] = 1;
    for (int nbr : adj[loc]) if (nbr != par) {
        int res = centroid(adj, subt, nbr, loc);
        subt[loc] += subt[nbr];
        if (res != -1) ret = res;
        bad |= subt[nbr] * 2 > sz(adj);
    }
    if (ret != -1) return ret;
    bad |= (sz(adj) - subt[loc]) * 2 > sz(adj);
    return bad ? -1 : loc;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int N;
    cin >> N;

    vvi adj(N);
    for (int i = 0, u, v; i < N - 1; i++) {
        cin >> u >> v;
        adj[u-1].push_back(v-1);
        adj[v-1].push_back(u-1);
    }

    vi subt(N);
    int cent = centroid(adj, subt, 0, 0);

    vi sizes;
    for (int nbr : adj[cent]) if (subt[nbr] < subt[cent]) {
        sizes.push_back(subt[nbr]);
    }
    if (cent != 0) sizes.push_back(N - subt[cent]);
    sizes.push_back(1);

    const int T = sz(sizes);

    vvmn pref(T + 1, vmn(N + 1));

    pref[0][0] = 1;

    for (int i = 0; i < T; i++) {
        for (int f = 0; f <= N; f++) if (pref[i][f].v) {
            for (int a = 0; a <= sizes[i]; a++) {
                pref[i+1][f+a] += pref[i][f] * mn::ncr(sizes[i], a)
                    * mn::fact(sizes[i]) / mn::fact(sizes[i] - a);
            }
        }
    }

    mn ans = 0;
    for (int f = 0; f < N; f++) {
        mn ways = pref[T - 1][f] * mn::fact(N - 1 - f);
        if (f&1) ans -= ways;
        else ans += ways;
    }
    for (int f = 0; f <= N; f++) {
        mn ways = pref[T][f] * mn::fact(N - f);
        if (f&1) ans -= ways;
        else ans += ways;
    }

    cout << ans << endl;

    return 0;
}

Submission Info

Submission Time
Task F - Squirrel Migration
User socketnaut
Language C++14 (GCC 5.4.1)
Score 800
Code Size 6150 Byte
Status
Exec Time 3746 ms
Memory 98560 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt
All 800 / 800 0_00.txt, 0_01.txt, 0_02.txt, 0_03.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt
Case Name Status Exec Time Memory
0_00.txt 1 ms 256 KB
0_01.txt 1 ms 256 KB
0_02.txt 1 ms 256 KB
0_03.txt 1 ms 256 KB
1_00.txt 2053 ms 1024 KB
1_01.txt 2054 ms 1024 KB
1_02.txt 1380 ms 640 KB
1_03.txt 2648 ms 768 KB
1_04.txt 2050 ms 640 KB
1_05.txt 2738 ms 768 KB
1_06.txt 3718 ms 2048 KB
1_07.txt 3746 ms 2048 KB
1_08.txt 829 ms 49536 KB
1_09.txt 885 ms 98560 KB
1_10.txt 1711 ms 49664 KB
1_11.txt 2297 ms 49664 KB
1_12.txt 3606 ms 2560 KB
1_13.txt 2026 ms 640 KB
1_14.txt 2569 ms 768 KB
1_15.txt 2678 ms 768 KB
1_16.txt 3048 ms 768 KB
1_17.txt 3405 ms 896 KB
1_18.txt 3634 ms 1024 KB
1_19.txt 3674 ms 1408 KB
1_20.txt 3619 ms 2048 KB
1_21.txt 3699 ms 2048 KB
1_22.txt 3529 ms 3072 KB
1_23.txt 3267 ms 5504 KB
1_24.txt 2659 ms 10368 KB
1_25.txt 1830 ms 20224 KB
1_26.txt 1449 ms 24576 KB
1_27.txt 1242 ms 33152 KB
1_28.txt 937 ms 49408 KB
1_29.txt 1 ms 256 KB
1_30.txt 1 ms 256 KB
1_31.txt 2799 ms 768 KB
1_32.txt 2857 ms 896 KB
1_33.txt 2734 ms 896 KB
1_34.txt 2629 ms 896 KB
1_35.txt 2562 ms 896 KB
1_36.txt 2605 ms 896 KB