結果
問題 | No.794 チーム戦 (2) |
ユーザー |
|
提出日時 | 2019-02-22 23:10:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 49 ms / 1,500 ms |
コード長 | 1,414 bytes |
コンパイル時間 | 1,826 ms |
コンパイル使用メモリ | 174,644 KB |
実行使用メモリ | 11,136 KB |
最終ジャッジ日時 | 2024-11-25 21:52:48 |
合計ジャッジ時間 | 3,550 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;const ll MOD = 1000000007;ll modpow(ll x, ll n, ll mod = MOD) {ll res = 1;while (n > 0) {if (n & 1) res = res * x % mod;x = x * x % mod;n >>= 1;}return res;}ll calc(int num, vector<ll>& f, vector<ll>& fi) {ll res = 1;for (int i = num * 2; i >= 2; i -= 2) {ll tmp = i;tmp = tmp * (i-1) % MOD * fi[2] % MOD;(res *= tmp) %= MOD;}(res *= fi[num]) %= MOD;return res;}int main() {cin.tie(0);ios::sync_with_stdio(false);int n;ll K;cin >> n >> K;vector<ll> a(n);for (int i = 0; i < n; i++) cin >> a[i];sort(a.begin(), a.end(), greater<>());bool flag = true;for (int i = 0; i < n; i++) {int j = n - 1 - i;if (j < i) break;if (a[i] + a[j] > K) {flag = false;break;}}if (!flag) {cout << 0 << endl;return 0;}vector<ll> f(2 * n + 1, 1), fi(2 * n + 1, 1);for (int i = 1; i <= 2*n; i++) {f[i] = f[i-1]*i%MOD;}fi[2*n] = modpow(f[2*n], MOD - 2, MOD);for (int i = 2 * n; i > 0; i--) {fi[i-1] = fi[i]*i%MOD;}ll ans = 1;for (int i = 0, j = n - 1; i < n; i++) {while (j > i + 1) {if (a[j-1]+a[i]<=K) j--;else break;}if (j == i + 1) {int num = (n - 2 * i) / 2;if (num < 0) break;(ans *= calc(num, f, fi)) %= MOD;break;}int hoge = n - j - i;(ans *= hoge) %= MOD;}cout << ans << endl;return 0;}