题目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
     
      #include
      
       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<
       
        <<'\n';        return 0;    }    tem=fpow(n,n-4);    ans=ans*tem%mod;    cout<
        
         <<'\n';    return 0;}