【NOI2019模拟2019.7.1】为了部落（生成森林计数，动态规划）

待我称王封你为后i 2021-12-11 04:05 200阅读 0赞

### Description： ###

--------------------

![1399352-20190701214136199-324734811.png][]

\\(1<=n<=1e9,1<=m,k<=100\\)

模数不是质数。

### 题解： ###

--------------------

先选m个点，最后答案乘上\\(C\_\{n\}^m\\)。

不妨枚举m个点的度数和D，那么我们需要解决两个问题：

1.  一共m个有标号盒子，D个有标号小球放到盒子里，且每个盒子的球数不超过k的方案数。
2.  n-m个有标号点的D棵有根树的森林划分

#### Task1： ####

事实上这个东西可以直接NTT卷起来，效率应该是最高的，但是因为模数不是质数，所以不行。

设\\(f\[i\]\[j\]\\)表示i个盒子，j个小球的方案数。

不难得到一个容斥的转移：

\\(f\[i\]\[j\]=f\[i\]\[j-1\]\*i-f\[i-1\[j-(k+1)\]\*i\*C\_\{j-1\}^k\\)

组合数直接杨辉三角预处理。

复杂度：\\(O(m^2k)\\)

#### Task2： ####

利用扩展Cayley公式：

n个点，m棵树，且1-m的点在不同的树里的方案数：

拓展prufer序列的定义，现在是取出森林中最大的叶子，输出与它相邻的点，删掉它，直到剩下1..m

发现序列长度是n-m，且前n-1-m个位置可以填1..n，最后一个只能填1..m，所以：

\\(F(n,m)=m\*n^\{n-1-m\}\\)

那直接乘上一个\\(C\_n^m\\)来把1..m换成其它根即是我们要求的。

或者说直接推导：

新建一个虚点n+1，让所有的根连向n+1，那么就可以做树上purfer（取编号最小的叶子），直到剩下n+1一个点。

由于n+1的度数是m，所以在prufer序列中出现m-1次。

因此\\(=C\_\{n-1\}^\{m-1\}\*n^\{n-m\}\\)

和上面是等价的。

#### Task3： ####

\\(Ans=C(n,m)\*\\sum\_\{i=0\}^\{mk\}f\[m\]\[i\]\*C\_\{n-m-1\}^\{i-1\}\*(n-m)^\{n-m-i\}\\)

模数不是质数，所以组合数需要分解质因数来算。

### Code： ###

--------------------

#include<bits/stdc++.h>
    #define fo(i, x, y) for(int i = x, B = y; i <= B; i ++)
    #define ff(i, x, y) for(int i = x, B = y; i <  B; i ++)
    #define fd(i, x, y) for(int i = x, B = y; i >= B; i --)
    #define ll long long
    #define pp printf
    #define hh pp("\n")
    using namespace std;
    
    int T, n, m, k, mo;
    
    ll ksm(ll x, ll y) {
        ll s = 1;
        for(; y; y /= 2, x = x * x % mo)
            if(y & 1) s = s * x % mo;
        return s;
    }
    
    int u[105], v[105], u0;
    int pmo;
    
    void fen(int x) {
        pmo = x;
        u0 = 0;
        for(int i = 2; i * i <= x; i ++) if(x % i == 0) {
            u[++ u0] = i; v[u0] = 0;
            for(; x % i == 0; x /= i) v[u0] ++;
        }
        if(x > 1) u[++ u0] = x, v[u0] = 0;
        fo(i, 1, u0) pmo = pmo / u[i] * (u[i] - 1);
    }
    
    ll c[10005][105];
    
    ll inv(int x) { return ksm(x, pmo - 1);}
    
    struct nod {
        int v[11];
    };
    
    nod operator * (nod a, nod b) {
        a.v[0] = (ll) a.v[0] * b.v[0] % mo;
        fo(i, 1, u0) a.v[i] += b.v[i];
        return a;
    }
    nod operator / (nod a, nod b) {
        a.v[0] = (ll) a.v[0] * inv(b.v[0]) % mo;
        fo(i, 1, u0) a.v[i] -= b.v[i];
        return a;
    }
    
    nod p[10005], q[10005];
    
    void gg(int x, nod &p) {
        if(!x) {
            fo(i, 1, u0) p.v[i] = 0;
            p.v[0] = 1;
            return;
        }
        fo(i, 1, u0) {
            p.v[i] = 0;
            for(; x % u[i] == 0; x /= u[i]) p.v[i] ++;
        }
        p.v[0] = x;
    }
    
    void build(int n) {
        gg(0, p[0]);
        gg(0, q[0]);
        fo(i, 1, min(10000, n)) {
            gg(i, p[i]);
            p[i] = p[i - 1] * p[i];
            gg(n - i + 1, q[i]);
            q[i] = q[i - 1] * q[i];
        }
    }
    ll C(int x) {
        nod w = q[x] / p[x];
        ll s = w.v[0];
        fo(i, 1, u0) s = s * ksm(u[i], w.v[i]) % mo;
        return s;
    }
    
    ll f[105][10005];
    
    int main() {
        freopen("islands.in", "r", stdin);
        freopen("islands.out", "w", stdout);
        scanf("%d", &T);
        fo(ii, 1, T) {
            scanf("%d %d %d %d", &n, &m, &k, &mo);
            if(n - m == 0) {
                pp("%d\n", 1 % mo);
                continue;
            }
            fen(mo);
            fo(i, 0, 10000) {
                c[i][0] = 1;
                fo(j, 1, min(i, 100)) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mo;
            }
            build(n - m);
            memset(f, 0, sizeof f);
            fo(i, 1, m) {
                f[i][0] = 1;
                fo(j, 1, i * k) {
                    f[i][j] = f[i][j - 1] * i;
                    if(j >= k + 1) f[i][j] -= f[i - 1][j - (k + 1)] * c[j - 1][k] % mo * i;
                    f[i][j] = (f[i][j] % mo + mo) % mo;
                } 
            }
            ll ans = 0;
            fo(i, 0, m * k) {
                if(n - m - 1 - i >= 0) ans += f[m][i] * C(i) % mo * i % mo * ksm(n - m, n - m - 1 - i) % mo;
                if(n - m - 1 - i == -1) ans += f[m][i] * C(i) % mo;
            }
            build(n);
            ans = ans % mo * C(m) % mo;
            pp("%lld\n", ans);
        }
    }

转载于:https://www.cnblogs.com/coldchair/p/11117056.html

[1399352-20190701214136199-324734811.png]: /images/20211211/567c097c09984af59a3e0cf7fa224c02.png