链接：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
#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 < return 0;
}