結果

問題 No.802 だいたい等差数列
ユーザー SuikabaSuikaba
提出日時 2019-03-17 23:41:03
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 401 ms / 2,000 ms
コード長 2,977 bytes
コンパイル時間 2,235 ms
コンパイル使用メモリ 202,484 KB
実行使用メモリ 19,804 KB
最終ジャッジ日時 2023-09-22 14:39:32
合計ジャッジ時間 5,742 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,380 KB
testcase_07 AC 1 ms
4,380 KB
testcase_08 AC 2 ms
4,380 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 12 ms
17,276 KB
testcase_11 AC 15 ms
18,576 KB
testcase_12 AC 9 ms
9,852 KB
testcase_13 AC 15 ms
19,272 KB
testcase_14 AC 63 ms
13,044 KB
testcase_15 AC 148 ms
9,120 KB
testcase_16 AC 28 ms
14,688 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 2 ms
4,380 KB
testcase_19 AC 50 ms
9,496 KB
testcase_20 AC 397 ms
14,888 KB
testcase_21 AC 401 ms
19,708 KB
testcase_22 AC 16 ms
19,804 KB
testcase_23 AC 151 ms
7,868 KB
testcase_24 AC 2 ms
4,380 KB
testcase_25 AC 1 ms
4,376 KB
testcase_26 AC 5 ms
5,472 KB
testcase_27 AC 5 ms
5,012 KB
testcase_28 AC 136 ms
8,376 KB
testcase_29 AC 392 ms
19,748 KB
testcase_30 AC 1 ms
4,376 KB
testcase_31 AC 2 ms
4,376 KB
testcase_32 AC 1 ms
4,376 KB
testcase_33 AC 12 ms
9,632 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