Submission #906976
Source Code Expand
#include<stdio.h>
#include<stdlib.h>
#include<cstring>
#include<iostream>
#include<ctype.h>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<cmath>
#include<bitset>
#include<iomanip>
#include<complex>
#include<utility>
#define X first
#define Y second
#define REP_0(i,n) for(int i=0;i<(n);++i)
#define REP_1(i,n) for(int i=1;i<=(n);++i)
#define REP_2(i,a,b) for(int i=(a);i<(b);++i)
#define REP_3(i,a,b) for(int i=(a);i<=(b);++i)
#define REP_4(i,a,b,c) for(int i=(a);i<(b);i+=(c))
#define DOW_0(i,n) for(int i=(n)-1;-1<i;--i)
#define DOW_1(i,n) for(int i=(n);0<i;--i)
#define DOW_2(i,a,b) for(int i=(b);(a)<i;--i)
#define DOW_3(i,a,b) for(int i=(b);(a)<=i;--i)
#define FOREACH(a,b) for(typeof((b).begin()) a=(b).begin();a!=(b).end();++a)
#define RFOREACH(a,b) for(typeof((b).rbegin()) a=(b).rbegin();a!=(b).rend();++a)
#define PB push_back
#define PF push_front
#define MP make_pair
#define IS insert
#define ES erase
#define IT iterator
#define RI reserve_iterator
#define PQ priority_queue
#define LB lower_bound
#define UB upper_bound
#define ALL(x) x.begin(),x.end()
#define PI 3.1415926535897932384626433832795
#define EXP 2.7182818284590452353602874713527
using namespace std;
typedef long long LL;
typedef long double LD;
typedef double DB;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef pair<int,PII> PIII;
typedef pair<LD,int> PLDI;
typedef vector<PII> VII;
template<class T>
T Mul(T x,T y,T P){
T F1=0;
while(y)
{
if(y&1)
{
F1+=x;
if(F1<0||F1>=P)F1-=P;
}
x<<=1;
if(x<0||x>=P)x-=P;
y>>=1;
}
return F1;
}
template<class T>
T Pow(T x,T y,T P){
T F1=1;x%=P;
while(y)
{
if(y&1)
{
F1=Mul(F1,x,P);
}
x=Mul(x,x,P);
y>>=1;
}
return F1;
}
template<class T>
T Gcd(T x,T y){
if(y==0)return x;
T z;
while(z=x%y){
x=y,y=z;
}
return y;
}
template<class T>
void UpdateMin(T &x,T y){
if(y<x)
{
x=y;
}
}
template<class T>
void UpdateMax(T &x,T y){
if(x<y)
{
x=y;
}
}
template<class T>
T Sqr(const T x){
return x*x;
}
template<class T>
T Abs(const T x){
return x<0?-x:x;
}
#define MaxBuffer 20000000
class ReadBuffer{
private:
char buff[MaxBuffer];
char *buf;
public:
void init(int size=MaxBuffer)
{
fread(buff,1,size,stdin);
buf=buff;
}
template<class T>
bool readInteger(T &x)
{
x=0;
while(*buf&&isspace(*buf)) ++buf;
if(*buf==0) return false;
static bool flag;
flag=0;
if(*buf=='-') flag=true;
else x=*buf-'0';
while(isdigit(*++buf)) x=x*10+*buf-'0';
if(flag) x=-x;
return true;
}
template<class T>
bool readFloat(T &x)
{
long double nowpos=0.1;
x=0;
while(*buf&&isspace(*buf)) ++buf;
if(*buf==0) return false;
static bool flag,decimal;
decimal=flag=0;
if(*buf=='-') flag=true,++buf;
else if(*buf=='.') decimal=true;
while(isdigit(*buf)||*buf=='.')
{
if(*buf=='.') decimal=true;
else
{
if(decimal)
{
x+=nowpos*(*buf-'0');
nowpos*=0.1;
}
else
{
x=x*10+*buf-'0';
}
}
++buf;
}
return true;
}
bool readChar(char c)
{
if(*buf==0) return 0;
return c=*buf++,1;
}
bool readString(char *s)
{
while(*buf&&isspace(*buf)) ++buf;
if(!*buf) return false;
while(!isspace(*buf)) *s++=*buf++;
*s++=0;
return true;
}
int countSpacetonext(){
int total=0;
while(*buf&&*buf==' ') ++total,++buf;
return total;
}
bool splitBycharactor(char *s,char Split='\n'){
while(*buf&&*buf!=Split) *s++=*buf++;
*s++=0;
return *buf!=0;
}
};
struct EDGE{
int T;EDGE *Nxt;
};
const int MOD = 924844033;
const int R = 5;
const int MAXN=524290;
namespace NTT{
inline int powmod(LL x, int y){
LL ret=1;
while(y){
if(y&1){
if(MOD<=(ret*=x)) ret%=MOD;
}
y>>=1;
if(MOD<=(x*=x)) x%=MOD;
}
return int(ret);
}
inline int inverse(int x){
return powmod(x, MOD - 2);
}
void NFT(int P[], int n, int oper) {
for (int i = 1, j = 0; i < n - 1; ++i) {
for (int s = n; j ^= s >>= 1, ~j & s;);
if (i < j) {
swap(P[i], P[j]);
}
}
for (int d = 0; (1 << d) < n; ++d) {
int m = 1 << d, m2 = m * 2;
int unit_p0 = powmod(R, (MOD - 1) / m2);
if (oper < 0) {
unit_p0 = inverse(unit_p0);
}
for (int i = 0; i < n; i += m2) {
int unit = 1;
for (int j = 0; j < m; ++j) {
int &P1 = P[i + j + m],
&P2 = P[i + j];
int t = (long long)unit * P1 % MOD;
P1 = (P2 - t + MOD) % MOD;
P2 = (P2 + t) % MOD;
unit = (long long)unit * unit_p0 % MOD;
}
}
}
}
int A[MAXN],B[MAXN];
void NTT(int FA[],int FB[],int len){
int N=1;
while(N<len*2){
N<<=1;
}
for(int i=0;i<len;++i){
A[i]=FA[i];
B[i]=FB[i];
}
for(int i=len;i<N;++i){
A[i]=B[i]=0;
}
NFT(A,N,1);
NFT(B,N,1);
for(int i=0;i<N;++i) A[i]=1LL*A[i]*B[i]%MOD;
NFT(A,N,-1);
long long tmp=inverse(N);
for(int i=0;i<N;++i){
FA[i]=A[i]*tmp%MOD;
}
}
}
long long fact[200001];
long long invfact[200001];
long long inv[200001];
vector<int> V[200001];
int sz[200001];
bool vis[200001];
void dfs(int x){
sz[x]=1;
vis[x]=1;
while(V[x].size()){
if(!vis[V[x].back()]){
dfs(V[x].back());
sz[x]+=sz[V[x].back()];
}
V[x].pop_back();
}
}
int FA[MAXN];
int FB[MAXN];
int main(){
fact[0]=invfact[0]=1;
for(int i=1;i<=200000;++i){
fact[i]=fact[i-1]*i%MOD;
inv[i]=i==1?1:MOD-MOD/i*inv[MOD%i]%MOD;
invfact[i]=invfact[i-1]*inv[i]%MOD;
}
int N;
scanf("%d",&N);
for(int i=1;i<N;++i){
int x,y;
scanf("%d%d",&x,&y);
V[x].push_back(y);
V[y].push_back(x);
}
dfs(1);
for(int i=2;i<=N;++i){
FA[sz[i]]=(FA[sz[i]]+fact[sz[i]])%MOD;
FA[N-sz[i]]=(FA[N-sz[i]]+fact[N-sz[i]])%MOD;
}
for(int i=0;i<=N;++i){
FB[i]=invfact[N-i];
}
NTT::NTT(FA,FB,N+1);
for(int i=1;i<=N;++i){
long long tmp=N*fact[N]%MOD*invfact[i]%MOD*invfact[N-i]%MOD-(FA[N+i]*invfact[i])%MOD;
if(tmp<0) tmp+=MOD;
printf("%d\n",int(tmp));
}
return 0;
}
Submission Info
Submission Time
2016-10-01 22:40:12+0900
Task
F - Many Easy Problems
User
rowdark
Language
C++14 (GCC 5.4.1)
Score
1900
Code Size
6207 Byte
Status
AC
Exec Time
250 ms
Memory
31104 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:306:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&N);
^
./Main.cpp:309:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&x,&y);
^
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
225 ms
26104 KB
doublestar1
AC
225 ms
26104 KB
doublestar2
AC
225 ms
26104 KB
doublestar3
AC
225 ms
26104 KB
doublestar4
AC
225 ms
26104 KB
example0
AC
13 ms
9600 KB
example1
AC
13 ms
9600 KB
example2
AC
13 ms
9600 KB
line0
AC
240 ms
30976 KB
line1
AC
240 ms
30976 KB
line2
AC
241 ms
31104 KB
line3
AC
237 ms
30976 KB
line4
AC
238 ms
30976 KB
maxrand0
AC
248 ms
25856 KB
maxrand1
AC
245 ms
25856 KB
maxrand10
AC
248 ms
25856 KB
maxrand11
AC
245 ms
25856 KB
maxrand12
AC
246 ms
25856 KB
maxrand13
AC
246 ms
25856 KB
maxrand14
AC
250 ms
25856 KB
maxrand15
AC
245 ms
25856 KB
maxrand16
AC
246 ms
25856 KB
maxrand17
AC
245 ms
25856 KB
maxrand18
AC
246 ms
25856 KB
maxrand19
AC
245 ms
25856 KB
maxrand2
AC
244 ms
25856 KB
maxrand3
AC
246 ms
25856 KB
maxrand4
AC
248 ms
25856 KB
maxrand5
AC
249 ms
25856 KB
maxrand6
AC
247 ms
25856 KB
maxrand7
AC
245 ms
25856 KB
maxrand8
AC
244 ms
25856 KB
maxrand9
AC
249 ms
25856 KB
rand0
AC
16 ms
9856 KB
rand1
AC
13 ms
9600 KB
rand2
AC
15 ms
9728 KB
rand3
AC
16 ms
9856 KB
rand4
AC
14 ms
9728 KB
rand5
AC
16 ms
9856 KB
rand6
AC
14 ms
9728 KB
rand7
AC
16 ms
9856 KB
rand8
AC
13 ms
9600 KB
rand9
AC
14 ms
9728 KB
star0
AC
215 ms
26484 KB
star1
AC
215 ms
26484 KB
star2
AC
216 ms
26484 KB
star3
AC
215 ms
26484 KB
star4
AC
214 ms
26484 KB