前言
模数要模 \(1e9+9\)！！模数要模 \(1e9+9\)！！模数要模 \(1e9+9\)！！
结论
\(n\) 个点的树的形态有 \((n-1)!\) 个，对于节点 \(k\)，它的所有度数和为 \((n-1)!\left(\sum\limits_{j=k+1}^n \dfrac{1}{j-1} + [k \not= 1] \right)\)
理论基础
树的形态
我们先说为什么 \(n\) 个点的树的形态有 \((n-1)!\) 种。
对于第 \(1\) 个点，加入后只有 \(1\) 种形态，且它是根节点，这是显然的。
对于第 \(2\) 个点，只能认 \(1\) 这个节点为爹，所以只有 \(1\) 种形态。
对于第 \(3\) 个点，能认的爹有 \(1\) 或者 \(2\)，所以总共有 \(2\) 种形态。
对于第 \(4\) 个点，对于之前两种形态的每一种，能认的爹有 \(1\) 或 \(2\) 或 \(3\)，所以总共有 \(2 \times 3\) 种形态。
我相信到这里你已经发现了其中的规律了！
对于第 \(i\) 个点，加入后树总共有 \((i-1)!\) 种。
所以 \(n\) 个点的树的形态有 \((n-1)!\) 种。
度数和
再来看为什么答案是 \((n-1)!\left(\sum\limits_{j=k+1}^n \dfrac{1}{j-1} + [k\not= 1] \right)\)
我们将这个式子拆成两部分：\((n-1)! \sum\limits_{j=k+1}^n \dfrac{1}{j-1}\) 和 \((n-1)! [k \not= 1]\)
我们先看较为简单的第二部分，度数=父亲节点数量+儿子节点数量，因为这是一棵树，所以每个非根节点有且只有一个父亲，根节点没有父亲，这就是公式第二部分的由来。
对于第一部分，对于每个点 \(k'\ (k < k' \le n)\)，它会在 \(1 \sim k'-1\) 中任意挑选一个爹，所以挑到点 \(k\) 当爹的概率自然是 \(\dfrac{1}{k'-1}\)。
细节处理
观察公式发现我们需要快速求出阶乘，这个很简单；还要快速求出逆元，这个用快速幂的话就超时了，所以用线性求逆元，不懂线性求逆元的可以戳我。
Code
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1e7 + 31;
const LL mod = 1e9 + 9;
int T, n, k;
LL inv[N], jc[N];
void init()
{
inv[1] = 1;
for (int i = 2; i < N; i ++ )
inv[i] = (mod - mod / i) * inv[mod % i] % mod;
for (int i = 2; i < N; i ++ ) inv[i] = (inv[i] + inv[i - 1]) % mod;
jc[1] = 1;
for (int i = 2; i < N; i ++ ) jc[i] = i * jc[i - 1] % mod;
return;
}
int main()
{
cin >> T;
init();
while (T -- )
{
cin >> n >> k;
LL ans;
if (k == 1) ans = (inv[n - 1] - inv[k - 1] + mod) % mod;
else ans = (inv[n - 1] - inv[k - 1] + 1 + mod) % mod;
ans = (ans * jc[n - 1]) % mod;
cout << ans << endl;
}
}
后语
概率/期望是真难，一天就做了俩绿题……
完结撒花，收~
标签：03,个点,int,题解,inv,生成器,jc,节点,mod From： https://www.cnblogs.com/LittleMoMol-kawayi/p/solution_LuoGu_P6862.html