結果

問題 No.1044 正直者大学
ユーザー yukinon0808yukinon0808
提出日時 2020-05-01 23:14:56
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 27 ms / 2,000 ms
コード長 5,816 bytes
コンパイル時間 1,723 ms
コンパイル使用メモリ 171,600 KB
実行使用メモリ 5,500 KB
最終ジャッジ日時 2023-08-26 15:48:28
合計ジャッジ時間 3,101 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,384 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 5 ms
5,500 KB
testcase_06 AC 27 ms
5,496 KB
testcase_07 AC 1 ms
4,376 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 5 ms
4,676 KB
testcase_13 AC 16 ms
4,632 KB
testcase_14 AC 5 ms
5,276 KB
testcase_15 AC 6 ms
5,108 KB
testcase_16 AC 18 ms
5,116 KB
testcase_17 AC 10 ms
4,588 KB
testcase_18 AC 12 ms
4,576 KB
testcase_19 AC 8 ms
4,440 KB
testcase_20 AC 5 ms
4,376 KB
testcase_21 AC 7 ms
4,380 KB
testcase_22 AC 3 ms
4,572 KB
testcase_23 AC 4 ms
5,204 KB
testcase_24 AC 4 ms
5,020 KB
testcase_25 AC 5 ms
5,104 KB
testcase_26 AC 5 ms
5,484 KB
testcase_27 AC 1 ms
4,376 KB
testcase_28 AC 1 ms
4,376 KB
testcase_29 AC 2 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define SZ(x) (int)(x.size())
#define REP(i, n) for(int i=0;i<(n);++i)
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RREP(i, n) for(int i=(int)(n)-1;i>=0;--i)
#define RFOR(i, a, b) for(int i=(int)(b)-1;i>=(a);--i)
#define ALL(a) a.begin(),a.end()
#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;
const double EPS = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
template <typename T1, typename T2>
bool chmax(T1 &a, const T2 &b) {
    if (a < b) { a = b; return true; }
    return false;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2 &b) {
    if (a > b) { a = b; return true; }
    return false;
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &mp);
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v);

template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    os << "(" << p.first << ":" << p.second << ")";
    return os;
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &mp) {
    os << "{";
    int a = 0;
    for (auto &tp : mp) {
        if (a) os << ", "; a = 1;
        os << tp;
    }
    return os << "}";
}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "[";
    REP(i, SZ(v)) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}

template<int64_t mod>
struct modint {
    using LL = int64_t;
    LL val;
    modint(LL val=0) : val(((val % mod) + mod) % mod) {}

    const modint operator+() const { return *this; }
    const modint operator-() const { return (-val + mod) % mod; }
    const modint inv() const { return pow(mod-2); }

    modint& operator+=(const modint& rhs) {
        (val += rhs.val) %= mod;
        return *this;
    }
    modint& operator-=(const modint& rhs) {
        return *this += -rhs;
    }
    modint& operator*=(const modint& rhs) {
        (val *= rhs.val) %= mod;
        return *this;
    }
    modint& operator/=(const modint& rhs) {
        return *this *= rhs.inv();
    }

    const modint operator+(const modint& rhs) const {
        return modint(*this) += rhs;
    }
    const modint operator-(const modint& rhs) const {
        return modint(*this) -= rhs;
    }
    const modint operator*(const modint& rhs) const {
        return modint(*this) *= rhs;
    }
    const modint operator/(const modint& rhs) const {
        return modint(*this) /= rhs;
    }

    const modint pow(LL n) const {
        modint ret = 1, tmp = val;
        while (n) {
            if (n & 1) ret *= tmp;
            tmp *= tmp; n >>= 1;
        }
        return ret;
    }

    bool operator==(const modint& rhs) const { return val == rhs.val; }
    bool operator!=(const modint& rhs) const { return !(*this == rhs); }

    friend const modint operator+(const LL& lhs, const modint& rhs) {
        return modint(lhs) + rhs;
    }
    friend const modint operator-(const LL& lhs, const modint& rhs) {
        return modint(lhs) - rhs;
    }
    friend const modint operator*(const LL& lhs, const modint& rhs) {
        return modint(lhs) * rhs;
    }
    friend const modint operator/(const LL& lhs, const modint& rhs) {
        return modint(lhs) / rhs;
    }

    friend bool operator==(const LL& lhs, const modint& rhs) {
        return modint(lhs) == rhs;
    }
    friend bool operator!=(const LL& lhs, const modint& rhs) {
        return modint(lhs) != rhs;
    }

    friend ostream& operator<<(ostream& os, const modint& a) {
        return os << a.val;
    }
    friend istream& operator>>(istream& is, modint& a) {
        LL tmp; is >> tmp;
        a = tmp;
        return is;
    }
};


template<typename Field>
struct Combination {
    vector<Field> _fact, _rfact, _inv;

    Combination(int n) : _fact(n), _rfact(n), _inv(n) {
        _fact[0] = _rfact[n-1] = 1;
        for (int i = 1; i < n; ++i) _fact[i] = _fact[i-1] * i;
        _rfact[n-1] /= _fact[n-1];
        for (int i = n-1; i > 0; --i) _rfact[i-1] = _rfact[i] * i;
        for (int i = 1; i < n; ++i) _inv[i] = _rfact[i] * _fact[i-1];
    }

    inline Field fact(int k) const { return _fact.at(k); }

    inline Field rfact(int k) const { return _rfact.at(k); }

    inline Field inv(int k) const { assert(k != 0); return _inv.at(k); }

    Field P(int n, int r) const {
        if (r < 0 or n < r) return 0;
        return fact(n) * rfact(n-r);
    }

    Field C(int n, int r) const {
        if (r < 0 or n < r) return 0;
        return fact(n) * rfact(r) * rfact(n-r);
    }

    Field H (int n, int r) const {
        return (n == 0 and r == 0) ? 1 : C(n+r-1, r);
    }
};


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    ll N, M, K; cin >> N >> M >> K;

    using Int = modint<MOD>;
    Combination<Int> comb(max(N, M)+1);

    if (N == 1) {
        if (K <= M-1) {
            cout << comb.fact(M) << endl;
        } else {
            cout << 0 << endl;
        }
        return 0;
    }

    Int ans = 0;
    for (int k = 1, updated = 1; updated; ++k) {
        updated = 0;
        if (K <= N + M - (2*k + 2)) {
            updated = 1;
            ans += comb.H(M-k, k) * comb.H(N-1-(k-1), (k-1));
        }
        if (K <= N + M - 2*k) {
            updated = 1;
            ans += comb.H(M-(k-1), (k-1)) * comb.H(N-1-k, k);
            ans += 2 * comb.H(M-(k-1), (k-1)) * comb.H(N-1-(k-1), (k-1));
        }
    }
    ans *= comb.fact(N-1) * comb.fact(M);

    cout << ans << endl;

    return 0;
}
0