Loading... ## 题意 给定一个完全二分图 $K_{n,m}$，然后问这个图生成树个数。 $n,m\leq 10^{18}$ ## 题解 考虑使用 Prufer 序列解决，由于 Prufer 序列最后会剩下两个点，并且由于这个题是二分图，所以一定剩下两个不同集合的点，那么每个集合分别会被删除 $n-1,m-1$ 次，每次删除都会把另一个集合的某个点放入 Prufer 序列，根据 Prufer 序列和生成树是双射，所以一共有 $n^{m-1}m^{n-1}$ 个生成树。 ```cpp #include<bits/stdc++.h> // #define ONLINE_JUDGE #define INPUT_DATA_TYPE long long #define OUTPUT_DATA_TYPE long long inline __attribute((always_inline)) INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10^48);return;} #define QPOW_DATA_TYPE __int128_t QPOW_DATA_TYPE QPOW_MOD=1000000007; QPOW_DATA_TYPE qpow(register QPOW_DATA_TYPE base,register QPOW_DATA_TYPE e){ register QPOW_DATA_TYPE res=1; base%=QPOW_MOD; while(e){ if(e&1) (res*=base)%=(QPOW_MOD); (base*=base)%=(QPOW_MOD); e>>=1; } return res; } int main(){ #ifndef ONLINE_JUDGE freopen("name.in", "r", stdin); freopen("name.out", "w", stdout); #endif long long n=read(); long long m=read(); QPOW_MOD=read(); print(qpow(n,m-1)*qpow(m,n-1)%QPOW_MOD); #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); #endif return 0; } ``` 最后修改：2024 年 04 月 21 日 © 允许规范转载 赞 如果觉得我的文章对你有用，使用点这里使用虚拟货币进行赞赏