Submission #1592788
Source Code Expand
#include "bits/stdc++.h" using namespace std; #define all(x) x.begin(), x.end() #define mp make_pair #define pii pair<int, int> #define ll long long static const int MOD = 924844033; long long inv(long long a) { long long res = 1; long long n = MOD - 2; while (n > 0) { if (n & 1) res = res * a % MOD; a = a * a % MOD; n >>= 1; } return res; } long long nCr(long long n, long long r) { if (n < r) return 0; if (n - r < r) r = n - r; long long ret = 1; for (int i = 0; i < r; i ++) { ret = ret * n % MOD; n --; ret = ret * inv(i + 1) % MOD; } return ret; } //long long fact[4040404]; //long long invfact[4040404]; //void init() { // fact[0] = 1; // for (int i = 1; i < 4040404; i ++) fact[i] = (fact[i - 1] * i) % MOD; // invfact[4040403] = inv(fact[4040403]); // for (int i = 4040402; i >= 0; i --) invfact[i] = (invfact[i + 1] * (i + 1)) % MOD; //} //long long nCr(long long n, long long r) { // if (n < r) return 0; // if (n - r < r) r = n - r; // return fact[n] * invfact[n - r] % MOD * invfact[r] % MOD; //} vector<int> g[200000]; int cnt[200000]; int n; int dfs(int v, int prev) { int sum = 0; for (auto u : g[v]) if (u != prev) { int get = dfs(u, v); cnt[get] ++; sum += get; } cnt[n - 1 - sum] ++; return sum + 1; } void solve() { cin >> n; assert(n <= 1000); for (int i = 0; i < n - 1; i ++) { int a, b; cin >> a >> b; a --, b --; g[a].push_back(b); g[b].push_back(a); } dfs(0, -1); for (int k = 1; k <= n; k ++) { long long ans = n * nCr(n, k) % MOD; for (int i = k; i <= n; i ++) if (cnt[i]) ans = (((ans - cnt[i] * nCr(i, k)) % MOD) + MOD) % MOD; cout << ans << endl; } return; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); //int T; //freopen("a.in", "r", stdin); //cin >> T; //while (T --) solve(); solve(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | F - Many Easy Problems |
User | KokiYmgch |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 2441 Byte |
Status | RE |
Exec Time | 1217 ms |
Memory | 5120 KB |
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 1900 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | example0, example1, example2 |
All | doublestar0, doublestar1, doublestar2, doublestar3, doublestar4, example0, example1, example2, line0, line1, line2, line3, line4, maxrand0, maxrand1, maxrand10, maxrand11, maxrand12, maxrand13, maxrand14, maxrand15, maxrand16, maxrand17, maxrand18, maxrand19, maxrand2, maxrand3, maxrand4, maxrand5, maxrand6, maxrand7, maxrand8, maxrand9, rand0, rand1, rand2, rand3, rand4, rand5, rand6, rand7, rand8, rand9, star0, star1, star2, star3, star4 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
doublestar0 | RE | 163 ms | 5120 KB |
doublestar1 | RE | 97 ms | 4992 KB |
doublestar2 | RE | 97 ms | 4992 KB |
doublestar3 | RE | 100 ms | 4992 KB |
doublestar4 | RE | 97 ms | 4992 KB |
example0 | AC | 3 ms | 4992 KB |
example1 | AC | 3 ms | 4992 KB |
example2 | AC | 3 ms | 4992 KB |
line0 | RE | 96 ms | 4992 KB |
line1 | RE | 97 ms | 4992 KB |
line2 | RE | 97 ms | 4992 KB |
line3 | RE | 97 ms | 4992 KB |
line4 | RE | 97 ms | 4992 KB |
maxrand0 | RE | 98 ms | 4992 KB |
maxrand1 | RE | 99 ms | 4992 KB |
maxrand10 | RE | 96 ms | 4992 KB |
maxrand11 | RE | 98 ms | 4992 KB |
maxrand12 | RE | 97 ms | 4992 KB |
maxrand13 | RE | 104 ms | 4992 KB |
maxrand14 | RE | 97 ms | 4992 KB |
maxrand15 | RE | 96 ms | 4992 KB |
maxrand16 | RE | 104 ms | 4992 KB |
maxrand17 | RE | 99 ms | 4992 KB |
maxrand18 | RE | 97 ms | 4992 KB |
maxrand19 | RE | 97 ms | 4992 KB |
maxrand2 | RE | 98 ms | 4992 KB |
maxrand3 | RE | 96 ms | 4992 KB |
maxrand4 | RE | 97 ms | 4992 KB |
maxrand5 | RE | 98 ms | 4992 KB |
maxrand6 | RE | 97 ms | 4992 KB |
maxrand7 | RE | 97 ms | 4992 KB |
maxrand8 | RE | 98 ms | 4992 KB |
maxrand9 | RE | 97 ms | 4992 KB |
rand0 | RE | 97 ms | 4992 KB |
rand1 | AC | 11 ms | 4992 KB |
rand2 | RE | 97 ms | 4992 KB |
rand3 | RE | 98 ms | 4992 KB |
rand4 | AC | 1217 ms | 4992 KB |
rand5 | RE | 97 ms | 4992 KB |
rand6 | RE | 98 ms | 4992 KB |
rand7 | RE | 98 ms | 4992 KB |
rand8 | AC | 190 ms | 4992 KB |
rand9 | RE | 98 ms | 4992 KB |
star0 | RE | 97 ms | 4992 KB |
star1 | RE | 99 ms | 4992 KB |
star2 | RE | 97 ms | 4992 KB |
star3 | RE | 99 ms | 4992 KB |
star4 | RE | 102 ms | 4992 KB |