Submission #910825
Source Code Expand
#include<stdio.h> #include<algorithm> #include<vector> using namespace std; long long mod=924844033; long long I=44009197; long long pw(long long a,long long b){ long long ret=1; while(b){ if(b%2)ret=ret*a%mod; b/=2; a=a*a%mod; } return ret; } void fft(int n, int p, long long a[]) { long long et=I; if(p==-1)et=pw(I,mod-2); for (int m = n; m >= 2; m >>= 1) { int mh = m >> 1; long long w=1; for (int i = 0; i < mh; i++) { for (int j = i; j < n; j += m) { int k = j + mh; long long x = mod+a[j] - a[k]; a[j] += a[k]; a[j]%=mod; a[k] = w * x; a[k]%=mod; } w*=et;w%=mod; } et=et*et%mod; } int i = 0; for (int j = 1; j < n - 1; j++) { for (int k = n >> 1; k > (i ^= k); k >>= 1); if (j < i) swap(a[i], a[j]); } } vector<int>g[210000]; long long inv[210000]; long long fact[210000]; long long factinv[210000]; int oc[210000]; int N; int dfs(int a,int b){ int sz=1; for(int i=0;i<g[a].size();i++){ if(g[a][i]==b)continue; sz+=dfs(g[a][i],a); } oc[sz]++; if(b!=-1)oc[N-sz]++; return sz; } long long x[1<<21]; long long y[1<<21]; int main(){ int a;scanf("%d",&a); N=a; for(int i=0;i<a-1;i++){ int p,q; scanf("%d%d",&p,&q); p--;q--;g[p].push_back(q);g[q].push_back(p); } inv[1]=fact[0]=factinv[0]=1; for(int i=2;i<210000;i++){ inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod; } for(int i=1;i<210000;i++)fact[i]=fact[i-1]*i%mod; for(int i=1;i<210000;i++)factinv[i]=factinv[i-1]*inv[i]%mod; int n=1<<21; long long ni=pw(n,mod-2); dfs(0,-1); for(int i=0;i<a;i++){ x[i]=oc[i]*fact[i]%mod; } for(int i=0;i<a;i++){ y[(1<<20)-i]=pw(fact[i],mod-2); } fft(1<<21,1,x); fft(1<<21,1,y); for(int i=0;i<(1<<21);i++)x[i]=x[i]*y[i]%mod;//for(int i=0;i<(1<<21);i++)if(x[i]<0)printf("%d: %lld\n",i,x[i]); fft(1<<21,-1,x); for(int i=0;i<(1<<21);i++)x[i]=x[i]*ni%mod; for(int i=1;i<=a;i++){ long long ks=pw(fact[i],mod-2); ks=ks*x[i+(1<<20)]%mod; long long ret=(a*fact[a]%mod*factinv[a-i]%mod*factinv[i]%mod+mod-ks)%mod; printf("%lld\n",ret); } } /* sum(j) a[j]*jCi = 1/(i!) sum(j) a[j]*(j!)/((j-i)!) = 1/(i!) sum(j) oc[j]*inv[(j-i)!] */
Submission Info
Submission Time | |
---|---|
Task | F - Many Easy Problems |
User | tozangezan |
Language | C++14 (GCC 5.4.1) |
Score | 1900 |
Code Size | 2252 Byte |
Status | AC |
Exec Time | 2807 ms |
Memory | 62464 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:59:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] int a;scanf("%d",&a); ^ ./Main.cpp:63:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d%d",&p,&q); ^
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 | 2626 ms | 51448 KB |
doublestar1 | AC | 2621 ms | 51320 KB |
doublestar2 | AC | 2665 ms | 51448 KB |
doublestar3 | AC | 2629 ms | 51448 KB |
doublestar4 | AC | 2711 ms | 51448 KB |
example0 | AC | 2336 ms | 42880 KB |
example1 | AC | 2382 ms | 42880 KB |
example2 | AC | 2356 ms | 42880 KB |
line0 | AC | 2627 ms | 62336 KB |
line1 | AC | 2692 ms | 62336 KB |
line2 | AC | 2663 ms | 62464 KB |
line3 | AC | 2659 ms | 62336 KB |
line4 | AC | 2621 ms | 62336 KB |
maxrand0 | AC | 2668 ms | 51456 KB |
maxrand1 | AC | 2695 ms | 51456 KB |
maxrand10 | AC | 2781 ms | 51584 KB |
maxrand11 | AC | 2753 ms | 51456 KB |
maxrand12 | AC | 2620 ms | 51456 KB |
maxrand13 | AC | 2707 ms | 51456 KB |
maxrand14 | AC | 2689 ms | 51456 KB |
maxrand15 | AC | 2661 ms | 51456 KB |
maxrand16 | AC | 2785 ms | 51456 KB |
maxrand17 | AC | 2661 ms | 51456 KB |
maxrand18 | AC | 2807 ms | 51456 KB |
maxrand19 | AC | 2752 ms | 51456 KB |
maxrand2 | AC | 2686 ms | 51456 KB |
maxrand3 | AC | 2724 ms | 51456 KB |
maxrand4 | AC | 2712 ms | 51456 KB |
maxrand5 | AC | 2690 ms | 51456 KB |
maxrand6 | AC | 2679 ms | 51584 KB |
maxrand7 | AC | 2656 ms | 51456 KB |
maxrand8 | AC | 2632 ms | 51456 KB |
maxrand9 | AC | 2684 ms | 51456 KB |
rand0 | AC | 2345 ms | 43008 KB |
rand1 | AC | 2380 ms | 42880 KB |
rand2 | AC | 2387 ms | 42880 KB |
rand3 | AC | 2356 ms | 43008 KB |
rand4 | AC | 2392 ms | 42880 KB |
rand5 | AC | 2297 ms | 43008 KB |
rand6 | AC | 2378 ms | 42880 KB |
rand7 | AC | 2350 ms | 43008 KB |
rand8 | AC | 2294 ms | 42880 KB |
rand9 | AC | 2315 ms | 42880 KB |
star0 | AC | 2675 ms | 51828 KB |
star1 | AC | 2699 ms | 51828 KB |
star2 | AC | 2629 ms | 51828 KB |
star3 | AC | 2672 ms | 51828 KB |
star4 | AC | 2621 ms | 51828 KB |