AtCoder Grand Contest 025 備忘録

前書き

AtCoder Grand Contest 025 に参加．解説聞いて解けそうだった問題の備忘録．

B問題

[問題はこちら]
・膨大なCombination計算をさせらタイムアウト地獄で挫折．そういうときはこう
(https://qiita.com/ofutonfuton/items/92b1a6f4a7775f00b6ae )．

・もう少し簡単に問題の解釈できた．
赤がA点，青がB点で，緑がA+B点なのだから，緑を塗るというより，重複を許して赤と青を塗る（赤と青が二色とも塗られている箇所が緑）と捉えれば良い．

以下はACのコード．

main.cpp

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

const ll M = 998244353;

vector<ll> fac(300001); //n!(mod M)
vector<ll> ifac(300001); //k!^{M-2} (mod M)
//a,bの範囲的にこれだけ配列を用意していけば十分

ll mpow(ll x, ll n){ //x^n(mod M) ←普通にpow(x,n)では溢れてしまうため，随時mod計算
    ll ans = 1;
    while(n != 0){
        if(n&1) ans = ans*x % M;
        x = x*x % M;
        n = n >> 1;
    }
    return ans;
}

ll comb(ll a, ll b){ //aCbをmod計算
    if(a == 0 && b == 0)return 1;
    if(a < b || a < 0)return 0;
    ll tmp = ifac[a-b]* ifac[b] % M;
    return tmp * fac[a] % M;
}

int main()
{
    ll n,a,b,k;
    cin >> n >> a>> b >> k;

    //大した量ではないので，先にfax[i]とifax[i]を全て計算しておく
    fac[0] = 1;
    ifac[0] = 1;
    for(ll i = 0; i<300000; i++){
        fac[i+1] = fac[i]*(i+1) % M; // n!(mod M)
        ifac[i+1] = ifac[i]*mpow(i+1, M-2) % M; // k!^{M-2} (mod M) ←累乗にmpowを採用
    }


    ll ans = 0;
    for(ll x = 0; x<=n; x++){
        if((k-a*x)%b !=0 ) continue;
        ll y = (k-a*x)/b;
        if(y<0 || y>n) continue;
        ans += comb(n, x)* comb(n, y) % M;
        ans %= M;
    }
    cout << ans << endl;

    return 0;
}

D問題

グラフ理論の知識が必要らしい...．

あとがき

精進します．