[AGC025 B] RGB Coloring

난이도: 1739

 

태그

• Combinatorics (조합론)
  • \( _{n}C_{r} \mod p \) \( (n, r \le p) \) in \( O(N) \) Precomputation & \( O(1) \) Query

 

풀이

1. 색깔을 칠하는 방식에 대해

문제에서 말한대로, 각 층에는 4가지 중 하나의 색깔을 칠할 수 있습니다.

 

하지만 4가지 색깔은 생각하기 어려우니까, \( A \)점의 색깔과 \( B \)점의 색깔 2가지만 고려해봅시다.

\( A+B \)점은 두 색깔을 동시에 사용하는 경우로, \( 0 \)점은 아무 색깔도 사용하지 않는 경우입니다.

 

이렇게 보면 색 \( A \)와 색 \( B \)는 독립적입니다.

풀어서 말하자면, 어떤 층에 \( A \)를 칠했는지와는 관계없이 \( B \)를 칠하든 말든을 선택할 수 있다는 거죠.

 

2. 색깔을 칠하는 방식에 대해 2

모든 층에 대해 점수는 동일한 방식으로 적용되므로, 각각의 색을 사용한 횟수만 알고 있으면

탑 전체의 점수를 알 수 있게 됩니다.

 

3. 그럼 각 색깔을 사용한 횟수만 고려해보자.

\( A \)를 사용한 횟수를 \( c_{A} \), \( B \)를 사용한 횟수를 \( c_{B} \)라고 해봅시다.

그럼 탑의 점수는 \( A \cdot c_{A} + B \cdot c_{B} \)가 됩니다.

 

그런데, \( 0 \le c_{A}, c_{B} \le N \)입니다.

또한, \( c_{A} \)가 고정되면, \( K = A \cdot c_{A} + B \cdot c_{B} \)이므로 \( c_{B} = \frac{K - A \cdot c_{A}}{B} \)가 됩니다.

즉, \( c_{A} \)가 고정되면 \( c_{B} \)도 고정됩니다.

 

그러니, \( 0 \le c_{A} \le N \)에 대해 돌려보면서, 이에 맞는 \( c_{B} \)를 찾아보고, 이 때의 경우의 수를 구해봅시다.

 

4. 색깔을 사용한 횟수가 고정될 때, 가능한 경우의 수

어떤 색깔을 \( C \)회 사용하는 경우의 수는 \( _{N}C_{C} \)회가 됩니다.

 

(1번)에서 본 바와 같이, 두 색깔은 독립적으로 적용시킬 수 있으므로,

가능한 경우의 수는 \( _{N}C_{c_A} \times _{N}C_{c_B} \)회가 됩니다.

 

코드

(4번)을 \( 0 \le c_{A} \le N \)에 대해 돌려주면서, 경우의 수를 더해주면 됩니다.

const ll mod = 998244353;
 
const int N = 300000;
ll fac[300020], inv[300020];
ll fpow(ll mul, ll bit){ ll res = 1;
    while (bit){
        if (bit&1){ res = res*mul % mod; }
        mul = mul*mul % mod; bit >>= 1;
    }
    return res;
}
inline ll finv(ll x){ return fpow(x, mod-2); }
 
inline ll ncr(int n, int r){
    if (0 > r || r > n){ return 0; }
    return fac[n] *inv[r] %mod *inv[n-r] %mod;
}
 
void Main(){
    fac[0] = 1; for (int i = 1; i <= N; i++){ fac[i] = fac[i-1]*i % mod; }
    inv[N] = finv(fac[N]); for (int i = N; i >= 1; i--){ inv[i-1] = inv[i]*i % mod; }
    int n; ll a, b, k; cin >> n >> a >> b >> k;
    ll ans = 0;
    for (int ac = 0; ac <= n; ac++){
        ll as = a*ac; ll bs = k-as;
        if (bs < 0 || bs%b != 0){ continue; }
        ll bc = bs/b;
        if (0 > bc || bc > n){ continue; }
        ans += ncr(n, ac) * ncr(n, bc) % mod; ans %= mod;
    }
    cout << ans;
}