309939: CF1762E. Tree Sum
Memory Limit:256 MB
Time Limit:3 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Tree Sum
题目描述
Let us call an edge-weighted tree with $ n $ vertices numbered from $ 1 $ to $ n $ good if the weight of each edge is either $ 1 $ or $ -1 $ and for each vertex $ i $ , the product of the edge weights of all edges having $ i $ as one endpoint is $ -1 $ . You are given a positive integer $ n $ . There are $ n^{n-2} \cdot 2^{n-1} $ distinct $ ^\dagger $ edge-weighted trees with $ n $ vertices numbered from $ 1 $ to $ n $ such that each edge is either $ 1 $ or $ -1 $ . Your task is to find the sum of $ d(1,n)^\ddagger $ of all such trees that are good. Since the answer can be quite large, you only need to find it modulo $ 998\,244\,353 $ . $ ^\dagger $ Two trees are considered to be distinct if either: - there exists two vertices such that there is an edge between them in one of the trees, and not in the other. - there exists two vertices such that there is an edge between them in both trees but the weight of the edge between them in one tree is different from the one in the other tree. Note that by [Cayley's formula](https://rb.gy/hho7vu), the number of trees on $ n $ labeled vertices is $ n^{n-2} $ . Since we have $ n-1 $ edges, there are $ 2^{n-1} $ possible assignment of weights(weight can either be $ 1 $ or $ -1 $ ). That is why total number of distinct edge-weighted tree is $ n^{n-2} \cdot 2^{n-1} $ . $ ^\ddagger $ $ d(u,v) $ denotes the sum of the weight of all edges on the unique simple path from $ u $ to $ v $ .输入输出格式
输入格式
The first and only line of input contains a single integer $ n $ ( $ 1 \leq n \leq 5 \cdot 10^5 $ ).
输出格式
The only line of output should contain a single integer, the required answer, modulo $ 998\,244\,353 $ .
输入输出样例
输入样例 #1
2
输出样例 #1
998244352
输入样例 #2
1
输出样例 #2
0
输入样例 #3
4
输出样例 #3
998244343
输入样例 #4
10
输出样例 #4
948359297
输入样例 #5
43434
输出样例 #5
86232114