首页 > 代码库 > 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 : 树的方差