链接：https://ac.nowcoder.com/acm/contest/21791/E
来源：牛客网

题目描述
岛上有三种颜色的岛屿，分别是红色、蓝色和紫色。岛群分别由

a
,
b
a,b和

c
c个不同的岛组成。

在一些（可能全部或没有）岛屿之间建立了桥梁。一座桥双向连接两个不同的岛，长度为

1
1。对于任意两个相同颜色的岛，要么不能通过桥相互到达，要么它们之间的最短距离至少为

3
3。

Fire Sisters 已准备好迎接未知，但他们也想测试您的勇气。你来这里是为了找出在约束条件下建造所有桥梁的不同方法的数量，并给出模

998244353
998244353 的答案。如果存在一对岛，它们之间有一座桥，但另一种没有桥，则两种方法被认为是不同的。
输入描述:
输入包含三个空格分隔的整数

a
,
b
,
c
（
1
≤
a
,
b
,
c
≤
5000
）
a,b,c（1≤a,b,c≤5000），分别表示岛群中红色、蓝色和紫色的岛数。
输出描述:
输出一行包含一个整数，表示构建桥梁的不同方法的数量，模

998244353
998244353。
示例1
输入

复制
1 1 1
输出

复制
8
说明

在这个例子中，有 3 座可能建造的桥，并且没有任何桥的设置违反限制。因此答案是

2
3

8
2
3
=8。
示例2
输入

复制
1 2 2
输出

复制
63
说明

下图中，上方两个是有效结构，而下方两个是无效的。

示例3
输入

复制
1 3 5
输出

复制
3264
示例4
输入

复制
6 2 9
输出

复制
813023575

根据题意，两个同色的岛之间的最短距离为3等价于两个同色的岛屿之间不能有边相连，同时两个同色的岛屿也不能同时连接到同一个岛。这样就好办了，对于每两种颜色可以计算这两种颜色的岛之间的连边的方案数，然后由乘法原理把这三种方案数乘起来即可。对于A和B这两种颜色，如果他们之间的岛屿连边一定是一个类似二分图的形式，只需要枚举连的边的数量然后用组合数计算方案即可。形式化地来说，对于输入的a和b，若这两种颜色的岛屿的连边数为i，那么方案数就是\(C_{a}^{i}\times C_{b}^{i}\times i!\)，阶乘的话也很好理解。

// Created on 解志国的iPad.

#include <iostream>
#define ll long long
#define LL long long
#define mod 998244353
#define p 998244353
using namespace std;
ll a, b, c, ans = 1;
ll F(ll x) {
    ll ans = 1;
    for(int i = 1; i <= x; i++) {
        ans = ans * i % mod;
    }
    return ans;
}
const int maxn=1000005;
void extend_gcd(LL a,LL b,LL &x,LL &y){
    if(b==0){
        x=1,y=0;
        return;
    }
    extend_gcd(b,a%b,y,x);
    y-=a/b*x;
}

LL inv[maxn+10];
LL f[maxn+10];
void init(){//阶乘及其逆元打表
    f[0]=1;
    for(int i=1;i<=maxn;i++){
        f[i]=f[i-1]*i%p;
    }

    LL x,y;
    extend_gcd(f[maxn],p,x,y);//先求出f[N]的逆元，再循环求出f[1~N-1]的逆元
    inv[maxn]=(x%p+p)%p;
    for(int i=maxn-1;i>=1;i--){
        inv[i]=inv[i+1]*(i+1)%p;
    }
}

LL C(LL n,LL m){
    if(n==m||m==0)return 1;
    return (f[n]*inv[m]%p*inv[n-m]%p)%p;
}
int main() {
    init();
    cin >> a >> b >> c;
    ll ta = 0, tb = 0, tc = 0;
    for(ll i = 0; i <= min(a, b); i++) {
        ta = (ta + (C(a, i) * C(b, i) % mod * F(i) % mod) % mod) % mod;
    }
    for(ll i = 0; i <= min(b, c); i++) {
        tb = (tb + (C(b, i) * C(c, i) % mod * F(i) % mod) % mod) % mod;
    }
    for(ll i = 0; i <= min(a, c); i++) {
        tc = (tc + (C(a, i) * C(c, i) % mod * F(i) % mod) % mod) % mod;
    }
    cout << ta * tb % mod * tc % mod;
    return 0;
}