（今天碰到的题怎么这么小清新

$n$ 个不相同的点，$q$ 组询问，每次给定 $l,r$，问在 $n$ 个点中，选出 $x$ 个点 $(x \in [l,r])$，用边连起来，能构成多少种不同的树

$n,q \leq 10^6$

sol：

首先知道 $n$ 个点的树有 $n^{n-2}$ 个，因为这题标号不同就算不同，所以 $i$ 个点不同的树有 $C_n^i \times i^{i-2}$

维护一下这东西的前缀和就可以每组询问 $O(1)$ 了

#include <bits/stdc++.h>
#define LL long long
using namespace std;
#define rep(i, s, t) for (register int i = (s), i##end = (t); i <= i##end; ++i)
#define dwn(i, s, t) for (register int i = (s), i##end = (t); i >= i##end; --i)
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    for (; !isdigit(ch); ch = getchar())
        if (ch == '-')
            f = -f;
    for (; isdigit(ch); ch = getchar()) x = 10 * x + ch - '0';
    return x * f;
}
const int maxn = 1e6 + 10;
int n, T, mod, num[maxn], fac[maxn], ifac[maxn], cn[maxn], sum[maxn];
inline int ksm(int x, int t) {
    if (t < 0)
        return 0;
    if (t == 0)
        return 1;
    int res = 1;
    for (; t; x = 1LL * x * x % mod, t = t >> 1)
        if (t & 1)
            res = 1LL * x * res % mod;
    return res;
}
int main() {
    n = read(), T = read(), mod = read();
    rep(i, 1, n) num[i] = ksm(i, i - 2);
    ifac[0] = fac[0] = 1;
    rep(i, 1, n) fac[i] = 1LL * fac[i - 1] * i % mod;
    ifac[n] = ksm(fac[n], mod - 2);
    dwn(i, n - 1, 1) ifac[i] = 1LL * ifac[i + 1] * (i + 1) % mod;
    rep(i, 1, n) cn[i] = 1LL * (1LL * fac[n] * ifac[n - i] % mod) * ifac[i] % mod;
    rep(i, 1, n) sum[i] = (sum[i - 1] + (1LL * cn[i] * num[i] % mod)) % mod;
    while (T--) {
        int l = read(), r = read();
        int ans = (((sum[r] - sum[l - 1]) % mod) + mod) % mod;
        printf("%d\n", ans);
    }
}

View Code