Submission #2241982
Source Code Expand
//~ #pragma GCC optimize ("Ofast") #include <bits/stdc++.h> using namespace std; #define sim template < class c #define ris return * this #define dor > debug & operator << #define eni(x) sim > typename \ enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) { sim > struct rge {c b, e; }; sim > rge<c> range(c i, c j) { return rge<c>{i, j}; } sim > auto dud(c* x) -> decltype(cerr << *x, 0); sim > char dud(...); struct debug { #ifdef LOCAL ~debug() { cerr << endl; } eni(!=) cerr << boolalpha << i; ris; } eni(==) ris << range(begin(i), end(i)); } sim, class b dor(pair < b, c > d) { ris << "(" << d.first << ", " << d.second << ")"; } sim dor(rge<c> d) { *this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]"; } #else sim dor(const c&) { ris; } #endif }; #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " typedef long long ll; const int mod = 924844033; int add(int a, int b) { a += b; if(a >= mod) a -= mod; return a; } void add_self(int & a, int b) { a = add(a, b); } int mul(int a, int b) { return (ll) a * b % mod; } void mul_self(int & a, int b) { a = mul(a, b); } int my_pow(int a, int b) { int r = 1; while(b) { if(b % 2) mul_self(r, a); mul_self(a, a); b /= 2; } return r; } int my_inv(int a) { return my_pow(a, mod - 2); } #define div div_ok int div(int a, int b) { return mul(a, my_inv(b)); } int sub(int a, int b) { a -= b; if(a < 0) a += mod; return a; } #define REP(i,n) for(int i = 0; i < int(n); ++i) int gen; void dft(vector<int> & a, bool rev) { const int n = a.size(); for(int i = 1, k = 0; i < n; ++i) { for(int bit = n / 2; (k ^= bit) < bit; bit /= 2);;; if(i < k) swap(a[i], a[k]); } for(int len = 1, who = 0; len < n; len *= 2, ++who) { static vector<int> t[2][30]; vector<int> & om = t[rev][who]; if(om.empty()) { om.resize(len); om[0] = 1; int pierw = gen; //my_pow(3, 7 * 17); for(int rep = 0; rep < 20 - who; ++rep) pierw = mul(pierw, pierw); if(rev) pierw = my_inv(pierw); for(int i = 1; i < len; ++i) om[i] = mul(om[i-1], pierw); } for(int i = 0; i < n; i += 2 * len) REP(k, len) { int x = a[i+k]; int y = mul(a[i+k+len], om[k]); a[i+k] = x + y; if(a[i+k] >= mod) a[i+k] -= mod; a[i+k+len] = x - y; if(a[i+k+len] < 0) a[i+k+len] += mod; } } int tmp = my_inv(n); if(rev) REP(i, n) a[i] = mul(a[i], tmp); } vector<int> multiply( vector<int> a, vector<int> b) { if(a.empty() || b.empty()) return {}; int n = a.size() + b.size(); /*vector<T> ans(n - 1); if(min(a.size(),b.size()) < 190) { // BRUTE FORCE REP(i, a.size()) REP(j, b.size()) ans[i+j] += a[i]*b[j]; return ans; } */ while(n&(n-1)) ++n; a.resize(n); b.resize(n); dft(a, false); dft(b, false); for(int i = 0; i < n; ++i) a[i] = mul(a[i], b[i]); dft(a, true); return a; } #define C C2 //~ #warning small nax //~ const int nax = 205; const int nax = 2e5 + 5; vector<int> w[nax]; int n; int subtree[nax], cnt[nax], fac[nax], inv_fac[nax]; int C(int a, int b) { assert(a >= b && b >= 0); return mul(fac[a], mul(inv_fac[b], inv_fac[a-b])); } void dfs(int a, int par) { subtree[a] = 1; for(int b : w[a]) if(b != par) { dfs(b, a); subtree[a] += subtree[b]; ++cnt[subtree[b]]; ++cnt[n-subtree[b]]; } } void read_uint(int *x){ char c=0; while(c<'0') c = getchar_unlocked(); *x = c-'0'; c = getchar_unlocked(); while(c>='0') { *x *= 10; *x += c-'0'; c = getchar_unlocked(); } } void write_uint(int x){ static char buf[13]=" \n"; if(x==0){ fputs_unlocked("0\n", stdout); return; } int i = 10; while(x) { buf[i--] = '0' + x % 10; x /= 10; } fputs_unlocked(buf+1+i, stdout); } bool okk(int x) { for(int rep = 0; rep < 20; ++rep) x = mul(x, x); if(x == 1) return false; return mul(x, x) == 1; } int main() { gen = 2; while(!okk(gen)) ++gen; fac[0] = 1; for(int i = 1; i < nax; ++i) fac[i] = mul(fac[i-1], i); inv_fac[nax-1] = my_inv(fac[nax-1]); for(int i = nax - 2; i >= 0; --i) inv_fac[i] = mul(inv_fac[i+1], i+1); //~ for(int i = 0; i < nax; ++i) inv_fac[i] = my_inv(fac[i]); //~ scanf("%d", &n); read_uint(&n); for(int rep = 0; rep < n - 1; ++rep) { int a, b; read_uint(&a); read_uint(&b); //~ scanf("%d%d", &a, &b); w[a].push_back(b); w[b].push_back(a); } dfs(1, -1); for(int i = 1; i <= n; ++i) mul_self(cnt[i], fac[i]); vector<int> a(n+1), b(n+1); for(int i = 0; i <= n; ++i) { a[i] = cnt[n-i]; b[i] = inv_fac[i]; } vector<int> c = multiply(a, b); for(int k = 1; k <= n; ++k) { int answer = c[n-k]; //~ for(int s = k; s <= n; ++s) //~ add_self(answer, mul(cnt[s], inv_fac[s-k])); mul_self(answer, inv_fac[k]); int whole = mul(n, C(n, k)); write_uint(sub(whole, answer)); } }\
Submission Info
Submission Time | |
---|---|
Task | F - Many Easy Problems |
User | Errichto |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 5097 Byte |
Status | CE |
Compile Error
./Main.cpp:231:1: error: stray ‘\’ in program }\ ^