UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#204080#2862. 背包tkswls1001769ms66896kbC++11733b2024-04-09 08:51:402024-04-09 13:32:10

answer

#include <bits/stdc++.h>
#define int long long
#pragma GCC optimize(2)
using namespace std;
int n, f[1000006], g[1000006];
// f: ab
//g :b
vector<int> son[1000005];
const int mod = 998244353;
inline void dfs(int p) {
	g[p] = f[p] = 1;
	int u, v;
	for (int i : son[p]) {
		dfs(i);
		u = f[p], v = g[p];
		f[p] = ((f[i] + g[i]) * u % mod + v * f[i] % mod) % mod;
		g[p] = v * (g[i] + f[i]) % mod;
//		cout << i << ' ' << p << " " << f[p] << " " << g[p] << "\n";
	}
//	cout << p << " " << f[p] << " " << g[p] << "\n";
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	int p;
	for (int i = 2; i <= n; i++) {
		cin >> p;
		son[p].push_back(i);
	}
	dfs(1);
	cout << f[1];
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 5ms
memory: 24748kb

input:

1000
1 1 3 4 1 2 1 4 6 6 11 12 7 5 6 16 14 12 11 20 19 19 21 16 16 23 23 20 21 23 29 32 33 28 35 31 ...

output:

159485356

result:

ok single line: '159485356'

Test #2:

score: 10
Accepted
time: 3ms
memory: 24748kb

input:

1000
1 1 3 1 4 3 2 7 3 3 3 8 9 6 13 10 15 9 15 12 20 14 23 20 17 18 22 23 28 25 31 29 29 29 35 27 29...

output:

699022696

result:

ok single line: '699022696'

Test #3:

score: 10
Accepted
time: 4ms
memory: 24748kb

input:

1000
1 1 2 3 3 3 7 4 4 8 6 6 7 8 13 7 17 14 17 19 14 22 18 21 25 25 21 22 29 29 28 24 24 33 27 36 33...

output:

405811876

result:

ok single line: '405811876'

Test #4:

score: 10
Accepted
time: 132ms
memory: 55952kb

input:

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

output:

24575778

result:

ok single line: '24575778'

Test #5:

score: 10
Accepted
time: 479ms
memory: 59008kb

input:

1000000
1 2 1 2 5 5 4 8 4 8 5 11 13 12 11 11 2 8 7 11 13 8 11 16 2 26 17 24 10 14 15 4 3 4 9 17 10 1...

output:

784124029

result:

ok single line: '784124029'

Test #6:

score: 10
Accepted
time: 466ms
memory: 58996kb

input:

1000000
1 2 2 3 2 4 4 5 9 1 11 1 7 3 5 2 16 4 1 2 3 2 8 3 23 4 16 16 13 7 12 2 22 13 16 31 26 35 36 ...

output:

906750140

result:

ok single line: '906750140'

Test #7:

score: 10
Accepted
time: 169ms
memory: 66896kb

input:

1000000
1 1 3 4 4 1 6 1 2 4 2 7 10 10 6 10 12 18 18 19 17 13 17 17 19 26 20 21 25 29 28 30 32 31 33 ...

output:

93765800

result:

ok single line: '93765800'

Test #8:

score: 10
Accepted
time: 185ms
memory: 66872kb

input:

1000000
1 2 2 4 1 1 4 8 3 3 2 8 9 14 12 15 8 9 18 19 14 22 17 16 16 20 21 28 25 25 31 24 28 31 31 29...

output:

432123498

result:

ok single line: '432123498'

Test #9:

score: 10
Accepted
time: 160ms
memory: 66884kb

input:

1000000
1 2 2 1 3 5 2 1 1 10 3 3 13 5 9 13 11 10 18 16 14 15 14 22 20 17 22 21 29 24 30 28 33 33 31 ...

output:

124100566

result:

ok single line: '124100566'

Test #10:

score: 10
Accepted
time: 166ms
memory: 66876kb

input:

1000000
1 1 1 2 5 5 5 8 9 9 2 8 10 6 12 12 12 17 16 15 17 21 23 24 17 26 21 26 27 25 31 31 33 30 35 ...

output:

370799424

result:

ok single line: '370799424'

Extra Test:

score: 0
Extra Test Passed