結果

問題 No.802 だいたい等差数列
ユーザー SuikabaSuikaba
提出日時 2019-03-17 23:41:03
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 353 ms / 2,000 ms
コード長 2,977 bytes
コンパイル時間 1,714 ms
コンパイル使用メモリ 205,048 KB
実行使用メモリ 19,864 KB
最終ジャッジ日時 2024-07-08 06:14:41
合計ジャッジ時間 4,235 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 1 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 1 ms
6,944 KB
testcase_08 AC 1 ms
6,944 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 12 ms
17,400 KB
testcase_11 AC 13 ms
19,864 KB
testcase_12 AC 8 ms
9,048 KB
testcase_13 AC 13 ms
19,092 KB
testcase_14 AC 55 ms
14,164 KB
testcase_15 AC 130 ms
9,200 KB
testcase_16 AC 25 ms
13,444 KB
testcase_17 AC 2 ms
6,940 KB
testcase_18 AC 2 ms
6,940 KB
testcase_19 AC 44 ms
10,880 KB
testcase_20 AC 344 ms
15,188 KB
testcase_21 AC 353 ms
19,208 KB
testcase_22 AC 14 ms
19,636 KB
testcase_23 AC 130 ms
7,904 KB
testcase_24 AC 2 ms
6,944 KB
testcase_25 AC 2 ms
6,944 KB
testcase_26 AC 5 ms
6,940 KB
testcase_27 AC 4 ms
6,940 KB
testcase_28 AC 115 ms
9,432 KB
testcase_29 AC 336 ms
19,700 KB
testcase_30 AC 2 ms
6,940 KB
testcase_31 AC 2 ms
6,940 KB
testcase_32 AC 2 ms
6,940 KB
testcase_33 AC 10 ms
9,592 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

template <int Mod, bool IsPrime = false>
class mod_int {
    using ll = long long;

public:
    constexpr mod_int() : n(0) {}
    constexpr mod_int(int n_) : n(n_) {
        if(n >= Mod)     n %= Mod;
        else if(n < 0) n = (n % Mod + Mod) % Mod;
    }
    constexpr mod_int(ll n_) : n(n_) { n = (n + Mod) % Mod; }

    constexpr operator int() const { return n; }
    constexpr operator ll() const  { return n; }

    constexpr bool operator==(mod_int const& other) const { return n == other.n; }
    constexpr mod_int& operator+=(mod_int const& other) {
        if((n += other.n) >= Mod) n -= Mod;
        return *this;
    }
    constexpr mod_int& operator-=(mod_int const& other) {
        if((n += Mod - other.n) >= Mod) n -= Mod;
        return *this;
    }
    constexpr mod_int& operator*=(mod_int const& other) {
        n = (unsigned long long)n * other.n % Mod;
        return *this;
    }
    constexpr typename std::enable_if<IsPrime, mod_int>::type& operator/=(mod_int const& other) {
        return *this *= other.inverse();
    }
    constexpr mod_int operator+(mod_int other) const { return mod_int(*this) += other; }
    constexpr mod_int operator-(mod_int other) const { return mod_int(*this) -= other; }
    constexpr mod_int operator*(mod_int other) const { return mod_int(*this) *= other; }
    constexpr mod_int operator/(mod_int other) const { return mod_int(*this) /= other; }

    constexpr typename std::enable_if<IsPrime, mod_int>::type inverse() const {
        ll a = n, b = Mod, u = 1, v = 0;
        while(b) {
            ll t = a / b;
            a -= t * b; std::swap(a, b);
            u -= t * v; std::swap(u, v);
        }
        return mod_int(u);
    }

private:
    ll n;
};

template <int Mod, bool IsPrime>
std::ostream& operator<<(std::ostream& os, mod_int<Mod, IsPrime> const& n) {
    os << (int)n;
    return os;
}

constexpr int default_mod = 1000000007;

template <int Mod = default_mod>
mod_int<Mod, true> fact(int n) {
    static std::vector<mod_int<Mod, true>> v = {1};
    if(n >= static_cast<int>(v.size())) {
        const int from = v.size(), to = n + 1024;
        v.reserve(to);
        for(int i = from; i < to; ++i) {
            v.push_back(v.back() * mod_int<Mod, true>(i));
        }
    }
    return v[n];
}

template <int Mod = default_mod>
mod_int<Mod, true> comb(int n, int r) { // nCr
    if(r < 0 || r > n) return 0;
    return fact<Mod>(n) / fact<Mod>(r) / fact<Mod>(n - r);
}

using ll = long long;
using mint = mod_int<default_mod, true>; // default

int main() {
    ll n, m, d1, d2; cin >> n >> m >> d1 >> d2;
    const ll w = m - d1 * (n - 1) - 1;
    mint ans;
    for(int i = 0; i < n; ++i) {
        const ll t = w - (d2 - d1 + 1) * i;
        if(t < 0) continue;
        if(i & 1) {
            ans -= comb(n - 1, i) * comb(t + n, n);
        } else {
            ans += comb(n - 1, i) * comb(t + n, n);
        }
    }
    cout << ans << endl;
}
0