Submission #905189
Source Code Expand
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=924844033;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head
const int M=201000;
int sz[M],coef[M],n,u,v;
VI e[M];
void dfs(int u,int f) {
sz[u]=1;
for (auto v:e[u]) {
if (v==f) continue;
dfs(v,u);
coef[sz[v]]--;
sz[u]+=sz[v];
}
coef[n-sz[u]]--;
coef[n]++;
}
const int max0=1000000;
int N,L;
struct comp
{
double x, y;
comp(): x(0), y(0) { }
comp(const double &_x, const double &_y): x(_x), y(_y) { }
};
inline comp operator+(const comp &a, const comp &b) { return comp(a.x + b.x, a.y + b.y); }
inline comp operator-(const comp &a, const comp &b) { return comp(a.x - b.x, a.y - b.y); }
inline comp operator*(const comp &a, const comp &b) { return comp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x); }
inline comp conj(const comp &a) { return comp(a.x, -a.y); }
const double PI = acos(-1);
comp w[max0 + 5];
int bitrev[max0 + 5];
void fft(comp *a, const int &n) {
rep(i, 0, n) if (i < bitrev[i]) swap(a[i], a[bitrev[i]]);
for (int i = 2, lyc = n >> 1; i <= n; i <<= 1, lyc >>= 1)
for (int j = 0; j < n; j += i)
{
comp *l = a + j, *r = a + j + (i >> 1), *p = w;
rep(k, 0, i >> 1)
{
comp tmp = *r * *p;
*r = *l - tmp, *l = *l + tmp;
++l, ++r, p += lyc;
}
}
}
inline void fft_prepare()
{
rep(i, 0, N) bitrev[i] = bitrev[i >> 1] >> 1 | ((i & 1) << (L - 1));
rep(i, 0, N) w[i] = comp(cos(2 * PI * i / N), sin(2 * PI * i / N));
}
static comp a[max0 + 5], b[max0 + 5];
static comp ad[max0 + 5], bd[max0 + 5];
inline void conv(int *x, int *y, int *z,int K) {
N = (K + 1) << 1;
L = 0;
while ((1 << L) < N) ++L;
N = 1 << L;
fft_prepare();
rep(i, 0, K + 1) a[i] = comp(x[i] & 32767, x[i] >> 15);
rep(i, 0, K + 1) b[i] = comp(y[i] & 32767, y[i] >> 15);
rep(i, K + 1, N) a[i] = b[i] = comp(0, 0);
fft(a, N), fft(b, N);
rep(i, 0, N)
{
int j = (N - i) & (N - 1);
static comp da, db, dc, dd;
da = (a[i] + conj(a[j])) * comp(0.5, 0);
db = (a[i] - conj(a[j])) * comp(0, -0.5);
dc = (b[i] + conj(b[j])) * comp(0.5, 0);
dd = (b[i] - conj(b[j])) * comp(0, -0.5);
ad[j] = da*dc+da*dd*comp(0,1);
bd[j] = db*dc+db*dd*comp(0,1);
}
rep(i, 0, N) {
a[i] = ad[i];
}
rep(i, 0, N) b[i] = bd[i];
fft(a, N), fft(b, N);
rep(i, 0, N)
{
int da = (ll)(a[i].x / N + 0.5) % mod;
int db = (ll)(a[i].y / N + 0.5) % mod;
int dc = (ll)(b[i].x / N + 0.5) % mod;
int dd = (ll)(b[i].y / N + 0.5) % mod;
z[i] = (da + ((ll)(db + dc) << 15) + ((ll)dd << 30)) % mod;
}
}
int p[max0],q[max0],r[max0],fnv[M];
int main() {
scanf("%d",&n);
rep(i,1,n) {
scanf("%d%d",&u,&v);
e[u].pb(v); e[v].pb(u);
}
dfs(1,0);
p[0]=1;
rep(i,1,n+1) p[i]=(ll)p[i-1]*i%mod;
rep(i,0,n+1) fnv[i]=powmod(p[i],mod-2),q[i]=fnv[i];
rep(i,0,n+1) {
p[i]=(ll)p[i]*coef[i]%mod;
if (p[i]<0) p[i]+=mod;
}
reverse(q,q+n+1);
conv(p,q,r,n+1);
rep(i,1,n+1) {
int v=r[n+i];
v=(ll)v*fnv[i]%mod;
printf("%d\n",v);
}
}
Submission Info
Submission Time
2016-10-01 21:20:43+0900
Task
F - Many Easy Problems
User
apiad
Language
C++14 (GCC 5.4.1)
Score
1900
Code Size
3572 Byte
Status
AC
Exec Time
441 ms
Memory
109824 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:124:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:126:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&u,&v);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
1900 / 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
AC
418 ms
99064 KB
doublestar1
AC
403 ms
98808 KB
doublestar2
AC
403 ms
98808 KB
doublestar3
AC
401 ms
98808 KB
doublestar4
AC
411 ms
98808 KB
example0
AC
73 ms
83072 KB
example1
AC
73 ms
83072 KB
example2
AC
73 ms
83072 KB
line0
AC
430 ms
109824 KB
line1
AC
431 ms
109824 KB
line2
AC
433 ms
109824 KB
line3
AC
432 ms
109824 KB
line4
AC
436 ms
109824 KB
maxrand0
AC
441 ms
98944 KB
maxrand1
AC
431 ms
98944 KB
maxrand10
AC
423 ms
98944 KB
maxrand11
AC
428 ms
98816 KB
maxrand12
AC
430 ms
98944 KB
maxrand13
AC
424 ms
98944 KB
maxrand14
AC
431 ms
98944 KB
maxrand15
AC
417 ms
98944 KB
maxrand16
AC
416 ms
98944 KB
maxrand17
AC
417 ms
98944 KB
maxrand18
AC
416 ms
98944 KB
maxrand19
AC
429 ms
98944 KB
maxrand2
AC
420 ms
98944 KB
maxrand3
AC
431 ms
98944 KB
maxrand4
AC
437 ms
98944 KB
maxrand5
AC
425 ms
98944 KB
maxrand6
AC
433 ms
98944 KB
maxrand7
AC
427 ms
98944 KB
maxrand8
AC
428 ms
98944 KB
maxrand9
AC
438 ms
98944 KB
rand0
AC
86 ms
83328 KB
rand1
AC
73 ms
83072 KB
rand2
AC
74 ms
83200 KB
rand3
AC
86 ms
83328 KB
rand4
AC
84 ms
83200 KB
rand5
AC
86 ms
83328 KB
rand6
AC
84 ms
83200 KB
rand7
AC
76 ms
83328 KB
rand8
AC
73 ms
83072 KB
rand9
AC
84 ms
83200 KB
star0
AC
405 ms
99188 KB
star1
AC
387 ms
99188 KB
star2
AC
385 ms
99316 KB
star3
AC
384 ms
99188 KB
star4
AC
382 ms
99188 KB