Codeforces Round #439 (Div. 2) C题

题意：红蓝粉村庄分别有a,b,c个，建桥要求同色的村庄，要么不可达，要么最短路至少为3，问建立道路的方案数。

分析：题意很明显就是，同色村庄内部不能连边，只能异色村庄染色，而且要保证是个偶图。

那其实就是问分别为(a,b) (a,c) (b,c)的点集，偶图的数目，组合数搞一下就好了。

注意取模，大数据验证下是否合法。

#include<bits/stdc++.h>
#define LL long long
#define maxn 5100
const LL Mod = 998244353;
using namespace std;
LL pre[maxn],C[maxn][maxn];
LL ans = 1, res;
int n, a, b, c;
int main(){
    pre[0] = 1;
    for(int i = 1; i <= 5000; i ++){
        pre[i] = (pre[i-1] * (LL)i) % Mod;
    }
    C[0][0] = 1;
    for(int i = 1; i <= 5000; i ++){
        C[i][0] = C[i][i] = 1;
        for(int j = 1; j < i; j ++){
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % Mod;
        }
    }
    cin >> a >> b >> c;
    n = min(a,b), res = 0; 
    for(int i = 0; i <= n; i ++){
        res = ((res + ((((C[a][i] * C[b][i]) % Mod) * pre[i]) % Mod)) % Mod);
    }
    ans = (ans * res) % Mod;
    n = min(c,b), res = 0; 
    for(int i = 0; i <= n; i ++){
        res = ((res + ((((C[c][i] * C[b][i]) % Mod) * pre[i]) % Mod)) % Mod);
    }
    ans = (ans * res) % Mod;
    n = min(a,c), res = 0; 
    for(int i = 0; i <= n; i ++){
        res = ((res + ((((C[a][i] * C[c][i]) % Mod) * pre[i]) % Mod)) % Mod);
    }
    ans = (ans * res) % Mod;
    cout << ans % Mod;
    return 0;
}