Codeforces1113F. Sasha and Interesting Fact from Graph Theory（组合数学计数广义Cayley定理）

题目链接：传送门

思路：

　　计数。树的结构和边权的计数可以分开讨论。

　　①假设从a到b的路径上有e条边，那么路径上就有e-1个点。构造这条路径上的点有$A_{n-2}^{e-1}$种方案；

　　②这条路径的权值的选择，可以用隔板法来做，相当于用e-1个隔板分开m个球，要求每个区间至少有一个球，那么就相当于在m-1个间隙里插入e-1个隔板，有$C_{m-1}^{e-1}$种方案；

　　③在路径之外的点还有n-e-1个，对应有n-e-1条边，每条边的权值可取[1, m]，所以有m^n-e-1种方案；

　　④在路径之外的点构造成树，相当于把剩下的点挂在之前的e+1个点上。这等价于从n个点建一个有e+1棵树，并且有e+1个节点分别在不同的树上，的森林。

　　根据广义Cayley定理可知，从x个点建一个有y棵树的森林，使得给定的y个节点各自属于不同的树上，的方案数为f(x, y) = y*x^x-y-1；

　　【此处广义Cayley的理解参考了jklover的博客】

　　因此有f(n, e+1)种方案。

　　综上所述，a到b的路径上有e条边的方案数为plan(e) = $A_{n-2}^{e-1}*C_{m-1}^{e-1}*m^{n-e-1}*f(n, e+1)$。

实现代码：

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6 + ;

const int md = 1e9 + ;

inline int add(int a, int b) {

    int res = (a+b)%md;

    if (res < )

        res += md;

    return res;

}

inline int mul(int a, int b) {

    return (int)(1LL * a * b % md);

}

int fpow(int a, int p) {

    int res = ;

    for (; p; p >>= ) {

        if (p & )

            res = mul(res, a);

        a = mul(a, a);

    }

    return res;

}

inline int f(int x, int y) {

    if (x == y)

        return ;

    return mul(y, fpow(x, x-y-));

}

int fac[MAX_N], inv[MAX_N];

void init() {

    fac[] = ;

    for (int i = ; i < MAX_N; i++)

        fac[i] = mul(fac[i-], i);

    inv[MAX_N-] = fpow(fac[MAX_N-], md-);

    for (int i = MAX_N-; i > ; i--)

        inv[i-] = mul(inv[i], i);

}

inline int A(int m, int n) {

    return mul(fac[m], inv[m-n]);

}

inline int C(int m, int n) {

    if (n > m)

        return ;

    return mul(A(m, n), inv[n]);

}

int main()

{

    init();

    int n, m, a, b;

    cin >> n >> m >> a >> b;

    int ans = ;

    for (int e = ; e <= n-; e++) {

        int tmp = ;

        tmp = mul(tmp, A(n-, e-));

        tmp = mul(tmp, C(m-, e-));

        tmp = mul(tmp, fpow(m, n-e-));

        tmp = mul(tmp, f(n, e+));

        ans = add(ans, tmp);

    }

    cout << ans << endl;

    return ;

}

好久没写博客了呀（计数器劝退），不过碰到好题还是忍不住要回来扯两句QwQ。

巴特西

Codeforces1113F. Sasha and Interesting Fact from Graph Theory（组合数学计数广义Cayley定理）

最新文章

热门文章

巴特西

Codeforces1113F. Sasha and Interesting Fact from Graph Theory（组合数学 计数 广义Cayley定理）

最新文章

热门文章

Codeforces1113F. Sasha and Interesting Fact from Graph Theory（组合数学计数广义Cayley定理）