LOJ6216 雪花挂饰

题目链接

从\(n\)片雪花里面选\(i\)个的方案数是\(\tbinom{n}{i}\)个.
根据Cayley定理,\(i\)个有标号的点形成无根树的方案数是\(i^{i-2}\).
所以选择\(i\)片雪花时的方案数是\(\tbinom{n}{i}i^{i-2}\).
对于一个区间答案是\(\sum\limits_{i=l}^{r}\tbinom{n}{i}i^{i-2}\).
因为询问较多可以用前缀和优化.
\(ans_{l,r}=(sum[r]-sum[l-1)\ mod\ P=(sum[r]\ mod\ P+sum[l-r]\ mod\ P)\ mod\ P\).
时间复杂度\(O(nlogn)\).

//CCCCCCCCCCCCCCCOrz
#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
int MOD, n, T, sum[N], fac[N], ifac[N];

int C(int n, int m) {
    return fac[n] * 1ll * ifac[m] % MOD * ifac[n - m] % MOD;
}
int fpow(int a, int b) {
    int ans = 1;
    for (; b; b >>= 1, a = a * 1ll * a % MOD) if (b & 1) ans = ans * 1ll * a % MOD;
    return ans;
}

int main() {
    scanf("%d%d%d",&n, &T, &MOD);
    fac[0] = ifac[0] = ifac[1] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i - 1] * 1ll * i % MOD;
    for (int i = 2; i <= n; i++) ifac[i] = (MOD - MOD / i) * 1ll * ifac[MOD % i] % MOD;
    for (int i = 2; i <= n; i++) ifac[i] = ifac[i - 1] * 1ll * ifac[i] % MOD;
    for (int i = 2; i <= n; i++) sum[i] = (sum[i - 1] * 1ll + fpow(i, i - 2) * 1ll * C(n, i)) % MOD;
    while(T--) {
        int l, r;
        scanf("%d%d", &l, &r);
        printf("%d\n", (sum[r] - sum[l - 1] + MOD) % MOD);
    }
    return 0;
}