ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#185709 | #3332. 化圆为方 | Crayon_ptwk | 100 | 5676ms | 385736kb | C++ | 994b | 2023-09-30 10:13:53 | 2023-09-30 12:43:10 |
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 1e7+10;
#define ll long long
const long long mod = 998244353;
int n;
ll sz[N],ans;
vector<int> g[N];
char ch;
inline int read(){
int res=0;
ch=getchar();
while(!(ch>='0'&&ch<='9')) ch=getchar();
while((ch>='0'&&ch<='9'))
res=(res<<3)+(res<<1)+ch-'0',ch=getchar();
return res;
}
inline ll kpow(ll a,ll b){
ll base=a,ret=1;
while(b){
if(b&1) ret=ret*base%mod;
base=base*base%mod;
b>>=1;
}
return ret%mod;
}
void dfs(int u,int dep){
if(g[u].size()==0){
sz[u]=1;
ans+=kpow(sz[u],mod-2);
return ;
}
for(int i=0;i<g[u].size();++i){
dfs(g[u][i],dep+1);
sz[u]+=sz[g[u][i]];
}
sz[u]++;
ans+=kpow(sz[u],mod-2);
ans%=mod;
}
int main(){
cin>>n;
for(int i=2,x;i<=n;++i)
x=read(),g[x].push_back(i);
dfs(1,1);
cout<<ans<<endl;
return 0;
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 53ms
memory: 235620kb
input:
10 1 1 3 1 4 6 6 7 8
output:
922187646
result:
ok 1 number(s): "922187646"
Test #2:
score: 10
Accepted
time: 29ms
memory: 235624kb
input:
10 1 2 3 2 3 2 2 4 9
output:
177465669
result:
ok 1 number(s): "177465669"
Test #3:
score: 10
Accepted
time: 48ms
memory: 235628kb
input:
10 1 1 1 1 3 4 6 7 7
output:
216286283
result:
ok 1 number(s): "216286283"
Test #4:
score: 10
Accepted
time: 189ms
memory: 250552kb
input:
999984 1 2 3 3 2 1 1 1 9 10 8 7 13 12 3 14 11 3 18 12 9 5 18 21 13 24 4 8 24 22 2 11 8 10 1 7 30 11 ...
output:
215590743
result:
ok 1 number(s): "215590743"
Test #5:
score: 10
Accepted
time: 208ms
memory: 250568kb
input:
999945 1 2 2 2 1 4 5 7 6 6 11 1 13 5 4 14 17 3 8 13 9 9 10 7 21 15 26 4 27 8 21 21 13 10 22 1 2 17 1...
output:
455596765
result:
ok 1 number(s): "455596765"
Test #6:
score: 10
Accepted
time: 192ms
memory: 250560kb
input:
999979 1 2 1 4 3 2 3 7 3 2 10 6 6 6 7 16 8 17 15 6 1 17 2 18 5 26 5 21 3 2 2 13 2 10 33 17 27 3 38 1...
output:
152327247
result:
ok 1 number(s): "152327247"
Test #7:
score: 10
Accepted
time: 196ms
memory: 250492kb
input:
999988 1 2 1 3 2 2 2 8 9 4 8 9 5 13 11 3 4 1 2 8 15 19 10 1 12 17 17 9 23 6 5 25 15 2 4 21 8 2 2 21 ...
output:
372616342
result:
ok 1 number(s): "372616342"
Test #8:
score: 10
Accepted
time: 1582ms
memory: 385716kb
input:
9999321 1 1 3 4 3 3 7 1 3 7 1 11 9 12 3 3 9 14 7 13 10 19 22 19 22 26 17 24 8 4 9 32 4 29 10 27 20 1...
output:
735203174
result:
ok 1 number(s): "735203174"
Test #9:
score: 10
Accepted
time: 1557ms
memory: 385736kb
input:
9999983 1 2 2 1 4 3 3 8 1 9 8 4 1 11 11 1 17 14 17 10 4 1 11 2 24 17 12 19 14 20 26 30 9 14 27 15 36...
output:
195679217
result:
ok 1 number(s): "195679217"
Test #10:
score: 10
Accepted
time: 1622ms
memory: 385688kb
input:
9999974 1 2 1 1 4 1 4 2 5 10 5 11 12 5 10 4 12 12 13 12 8 12 8 1 20 17 22 13 17 24 3 14 24 11 8 6 10...
output:
950738359
result:
ok 1 number(s): "950738359"