本文共 1543 字，大约阅读时间需要 5 分钟。

不会写,看的题解,emm,很厉害讷

为了方便解释,假设现在只需要考虑两个集合红,蓝(a,b)

$那么同集合间的点肯定不能连边,否则距离是1了$

$同色的点不能同时连到一个不同色的点去,否则距离是2了$

$综上所诉,连边的话最后的连通块要么是单独的一种颜色$

$要么是1个红点和1个蓝点组成的连通块$

$那么红点和蓝点组成的连通块最多有minn=min(a,b)个$

$所以对于i\in [0,minn],都是从红色中选i个点C_a^i$

$再从蓝点中选i个点C_b^i,然后i对红蓝点间连边有!i种可能$

好了,现在我们解决的两个集合a,b间连边,但是多加一个集合c进来呢?

$答案就是ab间连边可能\ast bc连边可能\ast ac连边可能$

$按照我们上面的考虑,同色点间的距离不会小于3$

#include 
   
    using namespace std;typedef long long ll;const ll maxn=5009;const ll mod =998244353;ll a,b,c,C[maxn][maxn],ans=1,fac[maxn];void init(){	C[0][0]=1,fac[0]=1;	for(int i=1;i<=5000;i++)	{		C[i][0]=1,fac[i]=fac[i-1]*(ll)i%mod;		for(int j=1;j<=i;j++)	C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;	}}void run(ll a,ll b){	ll minn=min(a,b),temp=0;	for(int i=0;i<=minn;i++)		temp=(temp+C[a][i]*C[b][i]%mod*fac[i]%mod)%mod;	ans=ans*temp%mod;}int main(){	cin >> a >> b >> c;	init();//求解组合数 	run(a,b);run(b,c);run(a,c);	cout<
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/107112672 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！