2020牛客暑期多校训练营（第一场）E、Counting Spanning Trees （图论、结论题）

题目链接

题面：

题意：
给定一张图，有左部和右部两部分顶点，对于每一个左部顶点 $u_i$ui​ 都与右部顶点 $v_1,v_2,...v_j$v1​,v2​,...vj​右部顶点的一个前缀相连。
问这张图生成树的个数。

题解：

我们设 $u_i$ui​ 的度数为 ${\lambda }_i$λi​， $v_j$vj​ 的度数为 ${\lambda }_j^{\prime }$λj′​，且满足 ${\lambda }_i>={\lambda }_{i+1},{\lambda }_i^{\prime }>={\lambda }_{i+1}^{\prime }$λi​>=λi+1​,λi′​>=λi+1′​。

设 $x_i,y_i$xi​,yi​分别为 $u_i,v_i$ui​,vi​的权值，一棵生成树T的权值为。
$sum\left(T\right)={\prod }_{i=1}^n{x}_i^{de{g}_T\left(u_i\right)}\cdot {\prod }_{j=1}^m{y}_j^{de{g}_T\left(v_j\right)}$sum(T)=∏i=1n​xidegT​(ui​)​⋅∏j=1m​yjdegT​(vj​)​

令 $\sum \left(G\right)={\sum }_{T}sum\left(T\right)$∑(G)=∑T​sum(T)

则生成树的个数 $cnt\left(G\right)=\sum \left(G\right){\mid }_{x_1=x_2=...=x_n=y_1=y_2=...=y_m=1}$cnt(G)=∑(G)∣x1​=x2​=...=xn​=y1​=y2​=...=ym​=1​

论文给出：
$\sum \left(G\right)=x_1\ast x_2\ast ...\ast x_n\ast y_1\ast y_2\ast ...\ast y_m\ast {\prod }_{i=2}^n(y_1+y_2+...+y_{{\lambda }_i})\ast {\prod }_{j=2}^m(x_1+x_2+...+x_{{\lambda }_j^{\prime }})$∑(G)=x1​∗x2​∗...∗xn​∗y1​∗y2​∗...∗ym​∗∏i=2n​(y1​+y2​+...+yλi​​)∗∏j=2m​(x1​+x2​+...+xλj′​​)

若所有的 x 与 y 均取 1。
$cnt\left(G\right)={\prod }_{i=2}^n{\lambda }_i\cdot {\prod }_{j=2}^m{\lambda }_j^{\prime }$cnt(G)=∏i=2n​λi​⋅∏j=2m​λj′​

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
using namespace std;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=998244353;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=100100;
const int maxm=100100;
const int up=100000;

ll a[maxn],b[maxn];
int main(void)
{
    int n,m,p;
    while(scanf("%d%d%d",&n,&m,&p)!=EOF)
    {
        for(int i=1;i<=m;i++)
            b[i]=0;
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]),b[1]++,b[a[i]+1]--;
        for(int i=1;i<=m;i++)
            b[i]+=b[i-1];
        sort(a+1,a+n+1);
        sort(b+1,b+m+1);
        ll ans=1;
        for(int i=n-1;i>=1;i--) ans=ans*a[i]%p;
        for(int i=m-1;i>=1;i--) ans=ans*b[i]%p;
        printf("%lld\n",ans);
    }
    return 0;
}