QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#291218#4811. Be CarefulRadewoosh#WA 1ms4412kbC++234.2kb2023-12-26 06:50:332023-12-26 06:50:33

Judging History

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

  • [2023-12-26 06:50:33]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4412kb
  • [2023-12-26 06:50:33]
  • 提交

answer

//~ while (clock()<=69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
//~ #pragma GCC target ("avx2")
//~ #pragma GCC optimize("Ofast")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//~ #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#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__) << "] "

#define shandom_ruffle random_shuffle

using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;
const int nax=207;
const ll mod=998244353;
//~ using bn=bitset<nax>;
const ll d=60;

struct bn
{
	ll wek[2];
	bn()
	{
		//~ wek.resize(4);
		for (int i=0; i<2; i++)
			wek[i]=0;
	}
	int daj(int v) const
	{
		return (wek[v/d]>>(v%d))&1;
	}
	void zapal(int v)
	{
		wek[v/d]|=(1LL<<(v%d));
	}
};

struct MyHash { std::size_t operator()(bn x) const
{
	ll ret=0;
	for (int i=0; i<2; i++)
		ret^=x.wek[i];
	return ret;
} };


bool operator==(const bn& a, const bn& b)
{
	for (int i=0; i<2; i++)
		if (a.wek[i]!=b.wek[i])
			return false;
	return true;
}

int n;

vi graf[nax];

int naj[nax];

ll dp[nax][nax];

bn pus;

bool operator <(const bn &a, const bn &b)
{
	//~ return a.wek<b.wek;
	for (int i=0; i<2; i++)
		if (a.wek[i]!=b.wek[i])
			return a.wek[i]<b.wek[i];
	return false;
}

int czylisc(int v)
{
	return graf[v].empty();
}

int moge(int v, int co)
{
	vi wek(co);
	for (int i : graf[v])
		wek[min(naj[i], co-1)]++;
	for (int i=co-1; i; i--)
	{
		if (wek[i]>1)
		{
			wek[i-1]+=wek[i]-1;
			wek[i]=1;
		}
	}
	for (int i : wek)
		if (!i)
			return 0;
	return 1;
}

void dfs0(int v, int oj)
{
	for (int &i : graf[v])
	{
		if (i==oj)
		{
			swap(i, graf[v].back());
			graf[v].pop_back();
			break;
		}
	}
	for (int i : graf[v])
		dfs0(i, v);
	
	if (czylisc(v))
	{
		naj[v]=n;
	}
	else
	{
		while(moge(v, naj[v]+1))
			naj[v]++;
	}
}

ll dppom[nax][nax];//iloma, iledziur

void dod(ll &a, ll b)
{
	a=(a+b)%mod;
}

bool mniej(int a, int b)
{
	return naj[a]>naj[b];
}

void dfs1(int v)
{
	if (czylisc(v))
		return;
	for (int i : graf[v])
		dfs1(i);
	unordered_map<bn, ll, MyHash> now, sta;
	int liscie=0;
	now[pus]=1;
	sort(graf[v].begin(), graf[v].end(), mniej);
	for (int i : graf[v])
	{
		if (czylisc(i))
		{
			liscie++;
			continue;
		}
		now.swap(sta);
		now.clear();
		for (int j=0; j<=naj[i]; j++)
		{
			int x=min(j, naj[v]+1);
			for (auto l : sta)
			{
				bn trz=l.first;
				trz.zapal(x);
				dod(now[trz], l.second*dp[i][j]);
			}
		}
	}
	for (auto i : now)
	{
		int brak=0;
		for (int j=0; j<=naj[v]; j++)
		{
			if (i.first.daj(j))
				continue;
			dod(dp[v][j], i.second*dppom[liscie][brak]);
			brak++;
		}
	}
}

int main()
{
	scanf("%d", &n);
	for (int i=1; i<n; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		graf[a].push_back(b);
		graf[b].push_back(a);
	}
	dfs0(1, 0);
	dppom[0][0]=1;
	for (int i=1; i<nax; i++)
	{
		dppom[i][0]=dppom[i-1][0]*n%mod;
		for (int j=1; j<=i; j++)
			dppom[i][j]=(dppom[i-1][j-1]*j+dppom[i-1][j]*(n-j))%mod;
	}
	dfs1(1);
	for (int i=0; i<=n; i++)
		printf("%lld\n", dp[1][i]);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4132kb

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: 1ms
memory: 4124kb

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: 1ms
memory: 4408kb

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: 0ms
memory: 4412kb

input:

2
1 2

output:

2
1
0

result:

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

Test #5:

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

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: 0ms
memory: 4132kb

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: 0ms
memory: 4152kb

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: 1ms
memory: 4120kb

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: 0ms
memory: 4120kb

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: 1ms
memory: 4152kb

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: 1ms
memory: 4112kb

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: 1ms
memory: 4216kb

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: 0ms
memory: 4140kb

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: 1ms
memory: 4168kb

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: 4404kb

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: -100
Wrong Answer
time: 1ms
memory: 4404kb

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:

wrong answer 121st numbers differ - expected: '693625848', found: '0'