AtCoder Grand Contest AGC025 B - RGB Coloring

B - RGB Coloring

問題へのリンク

解説

各マスの状態が4種類ある

• 
• 
• 
• 無

デフォルトを無だと考えて、そこに得点を割り振っていくと考えると、にするかしないかを独立に決めて、重なったらにすると考えればよいことがわかる。

よって、の個数をに決めれば、和がになるの個数は一意に定まり、

になる。ただしが条件。

の個数がそれぞれになるような塗り方はである。これをすべてのについて足し合わせればよい。

計算量は。

実装

• 提出へのリンク

struct mint {
};

struct combination {
}C(300010);

int main() {

    ll N, A, B, K;
    cin >> N >> A >> B >> K;
    mint ans = 0;
    for(ll i = 0; i <= N; i++){
        ll rem = K - A * i;
        if(rem < 0)continue;
        if(rem % B > 0)continue;
        ll j = rem / B;
        ans += C.Comb(N,i) * C.Comb(N,j);
    }
    cout << ans << endl;
}