首页 > 代码库 > hihoCoder挑战赛28 题目3 : 树的方差
hihoCoder挑战赛28 题目3 : 树的方差
题目3 : 树的方差
时间限制:20000ms
单点时限:1000ms
内存限制:256MB
描述
对于一棵 n 个点的带标号无根树，设 d[i] 为点 i 的度数。
定义一棵树的方差为数组 d[1..n] 的方差
给定 n ，求所有带标号的 n 个点的无根树的方差之和。
你需要将答案对 998244353 取模。
方差的定义：https://en.wikipedia.org/wiki/Variance
输入
仅一行：一个正整数 n
2 ≤ n ≤ 106
输出
仅一行：一个非负整数表示答案
样例解释
3个点的无根树有3种，每种的度数分布都是[1,2,1]
于是方差=((1-(4/3))2+(2-(4/3))2+(1-(4/3))2)/3=2/9
由于有3种，所以答案是2/3
分数取模的方法：https://math.stackexchange.com/questions/586595/finding-modular-of-a-fraction
- 样例输入
3
- 样例输出
665496236
#include<cstdio>#include<iostream>using namespace std;typedef long long ll;const ll mod=998244353;ll fpow(ll a,ll p){ ll res=1; for(;p;p>>=1,a=a*a%mod) if(p&1) res=res*a%mod; return res;}ll n,tem,ans;int main(){ cin>>n; ans=(n-2)*(n-1)%mod; if(n<=3){ tem=fpow(n,mod-2); ans=ans*tem%mod; cout<<ans<<‘\n‘; return 0; } tem=fpow(n,n-4); ans=ans*tem%mod; cout<<ans<<‘\n‘; return 0;}
hihoCoder挑战赛28 题目3 : 树的方差
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。