201 . 有號樹距離

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

100.0% (4/4)

Submission's AC Ratio

63.6% (7/11)

Tags

ioicamp ioicamp-2021

Description

對於一棵 $n$ 個點的樹，如果每個點上都有一個介於 $1$ 到 $n$ 之間的整數，並且任意兩個節點上的數字都不相同 ，那麼我們就稱這棵樹為一個有號樹。

考慮所有不同的具有 $n$ 個點的有號樹，定義其有趣值為樹上距離為 $2$ 的無序點對組數，請問隨機選取一棵有號樹其有趣值的期望值為多少？

已知答案必定可寫成 $\frac{p}{q}$ 的形式，請輸出 $p \cdot q^ {-1} \pmod{10^ 9 + 7}$。

Input Format

輸入只有一個正整數 $n$。

  • $1 \leq n \leq 10^ 6$

Output Format

對於每組輸入，若答案為 $\frac{p}{q}$，請輸出一個正整數 $p \cdot q^ {-1} \pmod{10^ 9 + 7}$。

Sample Input 1

3

Sample Output 1

1

Sample Input 2

4

Sample Output 2

250000004

Hints

如果存在某個正整數 $k$ ，在兩棵樹中和該節點 $k$ 相鄰的節點編號集合不同，我們就說兩棵有號樹是不同的。

Problem Source

IOICamp 2021 Day2 pA

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~117 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 1 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2
7 1000 262144 65536 2
8 1000 262144 65536 2
9 1000 262144 65536 2
10 1000 262144 65536 2
11 1000 262144 65536 2
12 1000 262144 65536 2
13 1000 262144 65536 2
14 1000 262144 65536 2
15 1000 262144 65536 2
16 1000 262144 65536 2
17 1000 262144 65536 2
18 1000 262144 65536 2
19 1000 262144 65536 2
20 1000 262144 65536 2
21 1000 262144 65536 2
22 1000 262144 65536 2
23 1000 262144 65536 2
24 1000 262144 65536 2
25 1000 262144 65536 2
26 1000 262144 65536 2
27 1000 262144 65536 2
28 1000 262144 65536 2
29 1000 262144 65536 2
30 1000 262144 65536 2
31 1000 262144 65536 2
32 1000 262144 65536 2
33 1000 262144 65536 2
34 1000 262144 65536 2
35 1000 262144 65536 2
36 1000 262144 65536 2
37 1000 262144 65536 2
38 1000 262144 65536 2
39 1000 262144 65536 2
40 1000 262144 65536 2
41 1000 262144 65536 2
42 1000 262144 65536 2
43 1000 262144 65536 2
44 1000 262144 65536 2
45 1000 262144 65536 2
46 1000 262144 65536 2
47 1000 262144 65536 2
48 1000 262144 65536 2
49 1000 262144 65536 2
50 1000 262144 65536 2
51 1000 262144 65536 2
52 1000 262144 65536 2
53 1000 262144 65536 2
54 1000 262144 65536 2
55 1000 262144 65536 2
56 1000 262144 65536 2
57 1000 262144 65536 2
58 1000 262144 65536 2
59 1000 262144 65536 2
60 1000 262144 65536 2
61 1000 262144 65536 2
62 1000 262144 65536 2
63 1000 262144 65536 2
64 1000 262144 65536 2
65 1000 262144 65536 2
66 1000 262144 65536 2
67 1000 262144 65536 2
68 1000 262144 65536 2
69 1000 262144 65536 2
70 1000 262144 65536 2
71 1000 262144 65536 2
72 1000 262144 65536 2
73 1000 262144 65536 2
74 1000 262144 65536 2
75 1000 262144 65536 2
76 1000 262144 65536 2
77 1000 262144 65536 2
78 1000 262144 65536 2
79 1000 262144 65536 2
80 1000 262144 65536 2
81 1000 262144 65536 2
82 1000 262144 65536 2
83 1000 262144 65536 2
84 1000 262144 65536 2
85 1000 262144 65536 2
86 1000 262144 65536 2
87 1000 262144 65536 2
88 1000 262144 65536 2
89 1000 262144 65536 2
90 1000 262144 65536 2
91 1000 262144 65536 2
92 1000 262144 65536 2
93 1000 262144 65536 2
94 1000 262144 65536 2
95 1000 262144 65536 2
96 1000 262144 65536 2
97 1000 262144 65536 2
98 1000 262144 65536 2
99 1000 262144 65536 2
100 1000 262144 65536 2
101 1000 262144 65536 2
102 1000 262144 65536 2
103 1000 262144 65536 2
104 1000 262144 65536 2
105 1000 262144 65536 2
106 1000 262144 65536 2
107 1000 262144 65536 2
108 1000 262144 65536 2
109 1000 262144 65536 2
110 1000 262144 65536 2
111 1000 262144 65536 2
112 1000 262144 65536 2
113 1000 262144 65536 2
114 1000 262144 65536 2
115 1000 262144 65536 2
116 1000 262144 65536 2
117 1000 262144 65536 2
Submit
Back to Top