CF869C The Intriguing Obsession

CF869C The Intriguing Obsession

考虑不合法的情况：

1.一个岛连接的两个岛颜色相同。

2.相同颜色的岛之间连接

我们发现第三种颜色不会影响前两种颜色之间的连接，于是我们可以把问题分成3部分， AB，AC，BC，最后相乘。

那么两种颜色之间连接方案数就是下面的公式了：

AB=sum_{i=0}^{min(a,b)}dbinom{a}{i}dbinom{b}{i}*i!

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;
const int N=5005; 
const int mod=998244353; 
typedef long long LL;
LL C[N][N],fac[N];
int a,b,c;
LL ans1,ans2,ans3;
int main() {
    scanf("%d%d%d",&a,&b,&c);
    fac[0]=1;
    for(int i=1;i<=5000;i++) fac[i]=fac[i-1]*i%mod;
    for(int i=0;i<=5000;i++) C[i][0]=C[i][i]=1;
    for(int i=1;i<=5000;i++)
        for(int j=1;j<i;j++)
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
    for(int i=0;i<=min(a,b);i++) 
        ans1=(ans1+C[a][i]*C[b][i]%mod*fac[i]%mod)%mod;
    for(int i=0;i<=min(c,b);i++) 
        ans2=(ans2+C[c][i]*C[b][i]%mod*fac[i]%mod)%mod;
    for(int i=0;i<=min(a,c);i++) 
        ans3=(ans3+C[a][i]*C[c][i]%mod*fac[i]%mod)%mod;
    printf("%lld
",ans1*ans2%mod*ans3%mod);
    return 0;
}