結果
| 問題 | No.1044 正直者大学 |
| ユーザー |
 yukinon0808
|
| 提出日時 | 2020-05-01 23:14:56 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 29 ms / 2,000 ms |
| コード長 | 5,816 bytes |
| コンパイル時間 | 2,166 ms |
| コンパイル使用メモリ | 172,592 KB |
| 実行使用メモリ | 5,632 KB |
| 最終ジャッジ日時 | 2024-12-25 14:19:41 |
| 合計ジャッジ時間 | 3,470 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 28 |
ソースコード
#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;}