QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#331779#4811. Be CarefulTokido_SayaWA 1ms8128kbC++145.2kb2024-02-18 19:22:552024-02-18 19:22:55

Judging History

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

  • [2024-02-18 19:22:55]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:8128kb
  • [2024-02-18 19:22:55]
  • 提交

answer

// Sea, You & Me
#include<bits/stdc++.h>
#define LL long long
#define DB double
#define MOD 998244353
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define lowbit(x) ((-x) & x)
#define MP make_pair
#define MT make_tuple
#define VI vector<int>
#define VL vector<LL>
#define VII VI::iterator
#define VLI VL::iterator
#define all(x) x.begin(), x.end()
#define EB emplace_back
#define PII pair<int, int>
#define SI set<int>
#define SII SI::iterator
#define fi first
#define se second
using namespace std;
template<typename T> void chkmn(T &a, const T b) { (a > b) && (a = b); }
template<typename T> void chkmx(T &a, const T b) { (a < b) && (a = b); }
void Inc(int &a, const int &b) { ((a += b) >= MOD) && (a -= MOD); }
void Dec(int &a, const int &b) { ((a -= b) < 0) && (a += MOD); }
void Mul(int &a, const int &b) { a = 1LL * a * b % MOD; }
void Sqr(int &a) { a = 1LL * a * a % MOD; }
int inc(const int &a, const int &b) { return (a + b >= MOD) ? a + b - MOD : a + b; }
int dec(const int &a, const int &b) { return (a - b < 0) ? a - b + MOD : a - b; }
int mul(const int &a, const int &b) { return 1LL * a * b % MOD; }
int sqr(const int &a) { return 1LL * a * a % MOD; }
int qwqmi(int x, int k = MOD - 2)
{
	int res = 1;
	while(k)
	{
		if(k & 1) Mul(res, x);
		k >>= 1, Sqr(x);
	}
	return res;
}
template<typename T> void read(T &x)
{
	x = 0;
	int f = 1;
	char ch = getchar();
	while(!isdigit(ch))
	{
		if(ch == '-')
			f = -1;
		ch = getchar();
	}
	while(isdigit(ch))
	{
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	x = x * f;
}
const int N = 205;
int n;
int qwq[N][N]; 
// qwq[i][j] : i^j
int deg[N], dcnt[N];
// dcnt[i] : the number of sons with deg <= i
vector<int> G[N], S1, S2;
// S1 is the set of sons with deg <= B, and S2 otherwise (leaves are not in consideration)
int f[N][N], suf[N][N];
// f[u][i] : the number when w[u] = i
// suf[u][i] : f[u][i] + f[u][i + 1] + ... + f[u][n]
int g[1 << 19];
// g[S] : the number of : take account of color <= B, the set of unselected colors is exactly S
int h[1 << 19][N];
// h[S][j] : the number of : take account the subset S of S2, order them to fill j unselected colors among [0, i](i is now possible ans)
int coef[1 << 19];
// coef[S] : the number of : take account the subset S of S2, order the color of sons in S to be > i(i is now possible ans)
void dfs(int u, int fa)
{
	// leaf
	if((int)G[u].size() == 1 && u != 1)
	{
		for(int i = 0; i <= n; ++i)
		{
			f[u][i] = 1;
			suf[u][i] = n - i + 1;
		}
		return;
	}
	
	// series of preprocess
	int leafcnt = 0;
	for(auto v : G[u])
	{
		if(v == fa) continue;
		dfs(v, u); ++deg[u];
		if(!deg[v]) ++leafcnt;
	}
	memset(dcnt, 0, sizeof(dcnt));
	for(auto v : G[u])
	{
		if(v == fa) continue;
		++dcnt[deg[v]];
	}
	for(int i = 1; i <= n; ++i)
		dcnt[i] += dcnt[i - 1];
	int B = 0, minx = N;
	for(int i = 0; i <= 18; ++i)
		if(i + dcnt[n] - dcnt[i] < minx)
			minx = i + dcnt[n] - dcnt[i], B = i;
	S1.clear(), S2.clear();
	for(auto v : G[u])
	{
		if(v == fa) continue;
		if(!deg[v]) continue;
		if(deg[v] <= B) S1.EB(v);
		else S2.EB(v);
	}
	int L = (int)S2.size();
	const int M1 = (1 << (B + 1));
	const int M2 = (1 << L);
	
	// calc g
	// First, calculate the number of  "the set of unselected colors is at least S"
	for(int S = 0; S < M1; ++S)
	{
		g[S] = 1;
		for(auto v : S1)
		{
			int sum = 0;
			for(int i = 0; i <= B; ++i)
				if((!(S >> i) & 1)) 
					Inc(sum, f[v][i]);
			Mul(g[S], sum);
		}
	}
	// Then, use SOSDP to calculate the true g[S]
	for(int i = 0; i <= B; ++i)
		for(int S = 0; S < M1; ++S)
			if(!((S >> i) & 1))
				Dec(g[S], g[S ^ (1 << i)]);
	
	// calc ans
	for(int _S = 0; _S < M1; ++_S)
	{
		if(!g[_S]) continue;
		for(int S = 0; S < M2; ++S)
			for(int i = 0; i <= deg[u]; ++i)
				h[S][i] = 0;
		h[0][0] = g[_S];
		for(int i = 0; i <= deg[u]; ++i)
		{
			// calc f
			if((_S & (1 << i)) || i > B) // may be w[u]
			{
				coef[0] = 1;
				for(int S = 1; S < M2; ++S)
				{
					int x = __builtin_ctz(S);
					coef[S] = mul(coef[S ^ (1 << x)], suf[S2[x]][i + 1]);
				}
				// inclusion and exclusion (actually superset inversion)
				for(int S = 0; S < M2; ++S)
					for(int j = 0; j <= deg[u]; ++j)
					{
						int val = mul(coef[(M2 - 1) ^ S], mul(h[S][j], qwq[n - j][leafcnt]));
						if(j & 1) Dec(f[u][i], val); else Inc(f[u][i], val);
					}
			}
			// calc h
			for(int j = i; j >= 0; --j)
			{
				// if i is free, consider to fill it
				if((_S & (1 << i)) || i > B)
				{
					for(int S = 0; S < M2; ++S)
						Inc(h[S][j + 1], h[S][j]);
				}
				// SOSDP
				for(int k = 0; k < L; ++k)
					for(int S = 0; S < M2; ++S)
						if(!((S >> k) & 1))
							Inc(h[S ^ (1 << k)][j], mul(h[S][j], f[S2[k]][i]));
			}
		}
	}
	
	// after-process
	for(int i = n; i >= 0; --i)
		suf[u][i] = inc(suf[u][i + 1], f[u][i]);
	while(!f[u][deg[u]]) --deg[u]; 
}
int main()
{
	read(n);
	for(int i = 1; i < n; ++i)
	{
		int x, y;
		read(x), read(y);
		G[x].EB(y), G[y].EB(x);
	}
	for(int i = 1; i <= n; ++i)
	{
		qwq[i][0] = 1;
		for(int j = 1; j <= n; ++j)
			qwq[i][j] = mul(qwq[i][j - 1], i);
	}
	dfs(1, 0);
	for(int i = 0; i <= n; ++i)
		printf("%d\n", f[1][i]);
	return 0;
}


详细

Test #1:

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

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

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

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

input:

2
1 2

output:

2
1
0

result:

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

Test #5:

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

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

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

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

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

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

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

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
0
710233310
10751559
76447757
959248417
24632015
777459888
618380400
0
0
0
0
0
0
0
0
0
0
0
0
0

result:

wrong answer 2nd numbers differ - expected: '242901486', found: '0'