oj.uz

Submission #627064

# Submission time Handle Problem Language Result Execution time Memory
627064 2022-08-12T06:19:35 Z AA_Surely LOSTIKS (INOI20_lostiks) C++14
0 / 100
 16 ms 20092 KB 
#include <bits/stdc++.h>

#define FOR(i, x, n) for(int i = x; i < n; i++)
#define F0R(i, n) FOR(i, 0, n)
#define ROF(i, x, n) for(int i = n - 1; i >= x; i--)
#define R0F(i, n) ROF(i, 0, n)

#define WTF cout << "WTF" << endl

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define F first
#define S second
#define PB push_back

#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()

using namespace std;

typedef long long LL;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;

const int N = 5e5 + 7;
const int LOG = 22;
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;

LL fact[N], ifact[N];
int ns[N], n, q;
VI adj[N];

inline int pw(LL a, int b) {
    LL ret = 1;
    for(; b; b >>= 1, a = a * a % MOD)
        if (b & 1) ret = ret *a % MOD;
    return ret;
}

void precalc() {
    fact[0] = 1;
    FOR(i, 1, N) fact[i] = fact[i - 1] * i % MOD;
    ifact[N - 1] = pw(fact[N - 1], MOD - 2);
    R0F(i, N - 1) ifact[i] = ifact[i + 1] * (i + 1) % MOD;
    return;
}

inline int nCr(int nn, int rr) {
    if (nn < rr || rr < 0) return 0;
    return (fact[nn] * ifact[rr] % MOD) * ifact[nn - rr] % MOD;
}

void init() {
    cin >> n >> ns[0];
    F0R(i, n - 1) {
        int u, v;
        cin >> u >> v;
        adj[--u].PB(--v);
        adj[v].PB(u);
    }

    cin >> q;
    return;
}

int main() {
    IOS;

    precalc();
    init();
        
    //cout << "nCr(" << ns[0] + n - 1 << ", " << n - 1 << ") " << endl;
    cout << nCr(ns[0] + n - 1, n - 1);
}

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 20092 KB Output is correct
2 Incorrect 16 ms 19872 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 19808 KB Output is correct
2 Incorrect 16 ms 19796 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 20092 KB Output is correct
2 Incorrect 16 ms 19872 KB Output isn't correct
3 Halted 0 ms 0 KB -