ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#204080 | #2862. 背包 | tkswls | 100 | 1769ms | 66896kb | C++11 | 733b | 2024-04-09 08:51:40 | 2024-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