QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#56839#4811. Be CarefulKING_UT#RE 6ms4092kbC++202.9kb2022-10-21 17:35:242022-10-21 17:35:27

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-21 17:35:27]
  • 评测
  • 测评结果:RE
  • 用时:6ms
  • 内存:4092kb
  • [2022-10-21 17:35:24]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
//#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)

#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)

#define bg begin()
#define ed end()
#define pb push_back
#define eb emplace_back
#define all(x) x.bg,x.ed
#define si(x) int(x.size())

template<class t>using vc=vector<t>;
template<class t>using vvc=vc<vc<t>>;

template<class t,class u>bool chmin(t&a,u b){
	if(a>b){a=b;return true;}
	else return false;
}
template<class t,class u>bool chmax(t&a,u b){
	if(a<b){a=b;return true;}
	else return false;
}

using pi=pair<int,int>;

bool add(vc<ll>&a,ll x){
	for(auto v:a)chmin(x,x^v);
	if(x)a.pb(x);
	return x;
}

using uint=unsigned;
const uint mod=998244353;
struct mint{
	uint v;
	mint(ll vv=0){s(vv%mod+mod);}
	mint& s(uint vv){
		v=vv<mod?vv:vv-mod;
		return *this;
	}
	mint operator -()const{return mint()-*this;}
	mint& operator+=(const mint&r){return s(v+r.v);}
	mint& operator-=(const mint&r){return s(v+mod-r.v);} 
	mint& operator*=(const mint&r){v=(unsigned ll)v*r.v%mod;return *this;}
	mint& operator/=(const mint&r){return *this*=r.inv();}
	
	mint operator+(const mint&r){return mint(*this)+=r;}
	mint operator-(const mint&r){return mint(*this)-=r;}
	mint operator*(const mint&r){return mint(*this)*=r;}
	mint operator/(const mint&r){return mint(*this)/=r;}
	
	mint pow(ll n)const{
		if(n<0)return inv().pow(-n);
		mint res(1),x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	mint inv()const{return pow(mod-2);}
};

mint parity(int i){
	return i&1?-1:1;
}

void slv(){
	int n;cin>>n;
	vvc<int> t(n);
	rep(_,n-1){
		int x,y;cin>>x>>y;
		x--;y--;
		t[x].pb(y);
		t[y].pb(x);
	}
	vvc<mint> dp(n,vc<mint>(n+1));
	vvc<mint> bin(n+1,vc<mint>(n+1));
	bin[0][0]=1;
	rep(i,n+1)rep(j,n+1){
		if(i)bin[i][j]+=bin[i-1][j];
		if(j)bin[i][j]+=bin[i][j-1];
	}
	vvc<mint> buf(n+1);
	rep(cnt,n+1){
		buf[cnt].resize(cnt+1);
		vc<mint> pn(n+1);
		rep(i,n+1)pn[i]=mint(i).pow(cnt);
		rep(hall,cnt+1){
			rep(c,hall+1){
				buf[cnt][hall]+=parity(c)*bin[hall-c][c]*pn[n-c];
			}
		}
	}
	
	vc<mint> cur;
	auto dfs=[&](auto self,int v,int p)->void{
		vc<pi> sc;
		for(auto ch:t[v])if(ch!=p){
			self(self,ch,v);
			int s=0;
			rep(i,n+1)if(dp[ch][i].v)s=i;
			sc.eb(s,ch);
		}
		if(sc.empty()){
			fill(all(dp[v]),1);
			return;
		}
		cur.clear();cur.pb(1);
		sort(all(sc));
		int cnt=0;
		for(auto [s,c]:sc){
			if(s<n){
				cur.resize(1<<(s+1));
				per(bit,si(cur)){
					mint w=cur[bit];
					cur[bit]=0;
					rep(i,s+1){
						cur[bit|1<<i]+=w*dp[c][i];
					}
				}
			}else{
				cnt++;
			}
		}
		rep(bit,si(cur)){
			int hall=0;
			rep(i,n+1){
				int z=0;
				if(i<30&&(bit&1<<i))z=1;
				if(z==0){
					dp[v][i]+=buf[cnt][hall]*cur[bit];
					hall++;
					if(hall>cnt)break;
				}
			}
		}
	};
	dfs(dfs,0,-1);
	rep(i,n+1)cout<<dp[0][i].v<<endl;
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	
	slv();
}

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3512kb

input:

5
1 2
1 3
2 4
2 5

output:

55
127
34
0
0
0

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 2ms
memory: 3568kb

input:

8
1 2
1 3
1 4
1 5
1 6
6 7
6 8

output:

69632
265534
133905
47790
12636
1944
0
0
0

result:

ok 9 numbers

Test #3:

score: 0
Accepted
time: 2ms
memory: 3576kb

input:

3
1 2
2 3

output:

1
3
0
0

result:

ok 4 number(s): "1 3 0 0"

Test #4:

score: 0
Accepted
time: 2ms
memory: 3552kb

input:

2
1 2

output:

2
1
0

result:

ok 3 number(s): "2 1 0"

Test #5:

score: 0
Accepted
time: 2ms
memory: 3652kb

input:

10
1 8
1 9
6 1
2 1
1 4
1 10
1 5
7 1
3 1

output:

1755647
612579511
359376750
200038110
104287680
49974120
21379680
7771680
2177280
362880
0

result:

ok 11 numbers

Test #6:

score: 0
Accepted
time: 2ms
memory: 3576kb

input:

10
2 8
2 9
6 2
2 1
2 4
2 10
2 5
7 2
3 2

output:

114358881
100000000
0
0
0
0
0
0
0
0
0

result:

ok 11 numbers

Test #7:

score: 0
Accepted
time: 2ms
memory: 3736kb

input:

10
7 8
8 9
6 5
2 1
3 4
9 10
4 5
7 6
3 2

output:

10
1
0
0
0
0
0
0
0
0
0

result:

ok 11 numbers

Test #8:

score: 0
Accepted
time: 2ms
memory: 3740kb

input:

10
3 6
2 4
4 9
8 4
2 5
10 5
3 7
2 1
1 3

output:

27510
31142
102399
0
0
0
0
0
0
0
0

result:

ok 11 numbers

Test #9:

score: 0
Accepted
time: 1ms
memory: 3652kb

input:

14
10 3
6 2
2 8
3 13
1 3
1 2
3 14
4 2
9 3
12 3
2 5
7 2
11 3

output:

930962871
780146137
253920328
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 15 numbers

Test #10:

score: 0
Accepted
time: 2ms
memory: 3724kb

input:

20
7 6
2 6
5 1
17 12
9 13
12 18
3 2
9 1
2 1
12 6
10 9
14 2
4 1
6 8
11 2
16 9
13 19
8 15
20 5

output:

572808214
694156482
763085092
958730326
465749894
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 21 numbers

Test #11:

score: 0
Accepted
time: 2ms
memory: 3516kb

input:

21
6 12
11 13
1 7
8 14
1 18
5 4
1 2
16 11
21 1
9 10
15 17
1 9
1 8
1 20
1 3
1 4
19 16
11 1
15 10
3 6

output:

778184256
242901486
277265229
855621813
564317020
918444623
408876720
314039448
593931360
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 22 numbers

Test #12:

score: 0
Accepted
time: 0ms
memory: 3568kb

input:

22
20 21
9 12
6 10
19 10
16 10
10 11
8 7
13 12
21 22
19 20
14 13
7 6
8 9
15 14
2 5
18 6
5 6
3 2
16 17
2 1
3 4

output:

142157709
5878180
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 23 numbers

Test #13:

score: 0
Accepted
time: 3ms
memory: 3520kb

input:

23
6 10
4 2
6 9
15 20
10 15
3 6
17 23
1 3
16 22
19 14
17 12
7 11
18 13
11 16
5 3
8 5
10 14
8 12
9 13
4 7
1 2
15 21

output:

7619809
175546557
7936610
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 24 numbers

Test #14:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

24
7 10
2 5
2 1
17 20
1 4
16 13
7 4
19 16
23 20
11 8
10 13
1 3
22 19
5 8
3 6
17 14
21 18
24 21
18 15
9 6
9 12
14 11
15 12

output:

24
576
15025
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 25 numbers

Test #15:

score: 0
Accepted
time: 0ms
memory: 3652kb

input:

24
22 16
17 11
15 9
13 7
8 2
1 3
5 1
6 12
9 3
14 8
21 15
17 23
19 13
7 1
24 18
2 1
5 11
1 4
4 10
18 12
20 14
10 16
1 6

output:

24
7962624
236177977
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

ok 25 numbers

Test #16:

score: 0
Accepted
time: 6ms
memory: 4092kb

input:

200
1 199
95 1
1 75
177 1
66 1
157 1
85 1
1 193
1 26
8 1
38 1
151 1
1 56
63 1
1 138
1 59
190 1
1 36
1 120
156 1
115 1
1 118
171 1
6 1
113 1
20 1
83 1
1 176
33 1
153 1
1 169
22 1
1 159
1 27
87 1
1 129
1 44
174 1
1 93
77 1
1 122
1 125
1 23
1 81
112 1
173 1
1 51
32 1
96 1
184 1
116 1
67 1
1 94
1 104
19...

output:

211917199
369375874
201944418
582671162
183066248
639389350
952947539
137147613
216366713
398936459
73236543
354059031
727857197
121548413
610762100
573534011
706945631
286154195
226699593
267771858
823273748
233587424
176942776
226493975
707601105
339075191
694353149
944734662
932707579
934386415
4...

result:

ok 201 numbers

Test #17:

score: -100
Runtime Error

input:

200
2 199
95 2
2 75
177 2
66 2
157 2
85 2
2 193
2 26
8 2
38 2
151 2
2 56
63 2
2 138
2 59
190 2
2 36
2 120
156 2
115 2
2 118
171 2
6 2
113 2
20 2
83 2
2 176
33 2
153 2
2 169
22 2
2 159
2 27
87 2
2 129
2 44
174 2
2 93
77 2
2 122
2 125
2 23
2 81
112 2
173 2
2 51
32 2
96 2
184 2
116 2
67 2
2 94
2 104
19...

output:


result: