Codeforces Round #439 (Div. 2) C. The Intriguing Obsession

C. The Intriguing Obsession

http://codeforces.com/contest/869/problem/C

(이 문제 너무 어려웠다 ㅠ.ㅠ 콘테중엔 나도 못풀었는데, 해설은 codeforces tutorial을 참고했다.)

(참고로 이 문제를 풀려면 페르마 소정리를 알고 있어야 한다. 모른다면 dp로 해결하는 수밖에 없다.)

이 문제는 경우의 수를 구하는 문제다.

섬이 3종류가 있고 섬들 간에 다리를 놓으려고 한다.

단 다리를 놓을 때 같은 색깔의 섬들은 최소 3의 길이가 되도록 놓아야 한다. (다리 하나는 길이 1을 의미한다.)

각 섬을 직접적으로 연결하는 다리는 하나만 놓을 수 있다.

(a,b를 직접적으로 연결하는 다리는 2개 이상 놓을 수 없다.)

입력은 다음과 같다.

Examples

input

1 1 1

output

8

input

1 2 2

output

63

input

1 3 5

output

3264

input

6 2 9

output

813023575

이 문제는 먼저 2개의 섬만 가지고 생각해봐야한다.

이런 생각을 시작해야 이 문제를 풀 수 있다.

1. 그럼 같은 색깔의 섬들 간의 거리가 최소3이란 뜻은 뭘까?

이 말은 같은 색깔의 섬들 간의 거리가 1이나 2이면 안된다는 뜻이다.

거리가 1일때는 같은 색깔의 섬들을 직접 연결한 경우이고,

거리가 2일때는 a0<->b0 연결을 하고 나서 b0를 다시 A의 섬인 a1과 연결한 경우이다. (N:N 매칭인 경우)

2. 그래프를 세 부분으로 쪼갤 수 있다.

위에서 거리가 1,2가 되지 않도록 두 섬들을 연결한다는 것은 1:1 매칭이 되도록 연결하거나 아예 연결을 하지 않는다는 뜻이다.

이런 방식으로 다리를 놓으면, A<->B 간의 다리를 놓는 경우가 B<->C or C<->A 간 다리를 놓는 경우에 아무런 영향을 주지 않는다. (독립)

그러므로 두 섬들간에 위와 같은 방법으로 다리를 놓는 경우를 다 더해서 마지막에 모두 곱해주면 답을 구할 수 있다.

코드는 아래와 같다.

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
int fact[5001], inv[5001];
const int MOD = 998244353;
int spow(int x, int k) {
    if(k==0) return 1;
    ll ret = spow(x,k>>1);
    if(k&1) return ret*ret%MOD*x%MOD;
    else return ret*ret%MOD;
}
inline int modinv(int x) { return spow(x,MOD-2); }
void init() {
    fact[0]=inv[0]=1;
    for(int i=1; i<=5000; i++) {
        fact[i] = (ll)fact[i-1]*i%MOD;
        inv[i] = modinv(fact[i]);
    }
}
ll C(int n, int k) {
    if(n<0||k<0||n<k) return 0LL;
    return (ll)fact[n]*inv[n-k]%MOD*inv[k]%MOD;
}
ll resA, resB, resC;
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    init();
    int a,b,c; cin >>a>>b>>c;
    int mx = max({a,b,c});
    for(int i=0; i<=mx; i++) {
        if(i<=a && i<=b) resA+=C(a,i)*C(b,i)%MOD*fact[i]%MOD, resA%=MOD;
        if(i<=b && i<=c) resB+=C(b,i)*C(c,i)%MOD*fact[i]%MOD, resB%=MOD;
        if(i<=c && i<=a) resC+=C(c,i)*C(a,i)%MOD*fact[i]%MOD, resC%=MOD;
    }
    cout << resA*resB%MOD*resC%MOD;
    return 0;
}