E 猜结论

题意

给一个特殊的二分图，要求你算出它生成树的个数，其中顶点数 $ n \le 10^5 $

思路

如果图的定点数小于 $ n \le 10^2 $，可以用矩阵树定理爆算，复杂度 $O(n^3)$

但是，这个图很大，尝试猜结论…

首先，从小图开始猜，比如样例3的基尔霍夫矩阵：

[ 1, 0, 0,-1, 0, 0 ],
[ 0, 2, 0,-1,-1,-1 ],
[ 0, 0, 3,-1,-1,-1 ],
[-1,-1,-1, 3, 0, 0 ],
[ 0,-1,-1, 0, 2, 0 ],
[ 0, 0,-1, 0, 0, 3 ]

其$n-1$阶余子式的值为 $ans = 1\times 2 \times 2 \times 1$, 因此答案为 $4$

比如样例2的基尔霍夫矩阵：

[ 2, 0,-1,-1 ],
[ 0, 2,-1,-1 ],
[-1,-1, 2, 0 ],
[-1,-1, 0, 2 ]

其$n-1$阶余子式的值为 $ans = 2 \times 2 $, 因此答案为 $4$

不妨猜，对这个特殊的二分图，记其度数序列为$deg(i)$，其答案为：

$ ans = \frac{\prod deg(x_i)deg(y_i)}{max(deg(x_i))max(deg(y_i))}$

代码

#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
int d[N], a[N];

int main() {
    int n, m, mod;
    while (~scanf("%d%d%d", &n, &m, &mod)) {
        long long ans = 1;
        
        for (int i = 1; i <= n; i++)
            d[i] = 0;

        for (int i = 1; i <= n; i++) {
            int x;
            scanf("%d", &a[i]);
            d[a[i]]++;
        }

        for (int i = m - 1; i; --i)
            d[i] += d[i + 1];

        swap(a[n], *max_element(a + 1, a + 1 + n));
        for (int i = 1; i < n; ++i)
            ans = ans * a[i] % mod;
        
        for (int i = 2; i <= m; i++) 
            ans = ans * d[i] % mod;
        printf("%lld\n", ans);
    }
    return 0;
}