結果
問題 | No.794 チーム戦 (2) |
ユーザー |
|
提出日時 | 2019-02-22 22:28:44 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 112 ms / 1,500 ms |
コード長 | 2,664 bytes |
コンパイル時間 | 905 ms |
コンパイル使用メモリ | 116,656 KB |
実行使用メモリ | 13,524 KB |
最終ジャッジ日時 | 2024-06-13 04:11:09 |
合計ジャッジ時間 | 3,733 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
コンパイルメッセージ
Main.d(36): Deprecation: foreach: loop index implicitly converted from `size_t` to `int`
ソースコード
import std.stdio, std.string, std.conv;import std.range, std.algorithm, std.array, std.typecons, std.container;import std.math, std.numeric, core.bitop;enum inf3 = 1_001_001_001;enum inf6 = 1_001_001_001_001_001_001L;enum mod = 1_000_000_007L;void main() {int n, k;scan(n, k);auto a = readArr!(int);auto as = a.sort();int m = 0;foreach (i ; 1 .. n) {if (as[i] + as[i - 1] <= k) {m = i;}}int[] usiro;foreach (i ; m + 1 .. n) {usiro ~= as[i];}debug {writeln(usiro);}long ans = 1;foreach (int i, u ; usiro.retro.array) {int p = as.lowerBound(k - u + 1).length.to!int;p = max(p - i, 0);ans *= p;ans %= mod;}int r = m + 1 - (n - m - 1);if (r <= 0) {writeln(0);return;}auto mc = ModComb(n);int rr = r;while (rr > 0) {ans *= mc.c(rr, 2);ans %= mod;rr -= 2;}ans *= mc.finv(r / 2);ans %= mod;writeln(ans);}struct ModComb {int _N;long[] _fact, _factinv;long _mod;this(int n, long mod = 1_000_000_007L) {_N = n;_fact = new long[](_N + 1);_factinv = new long[](_N + 1);_mod = mod;_fact[0] = 1;foreach (i ; 1 .. _N + 1) {_fact[i] = (_fact[i-1] * i) % mod;}_factinv[_N] = _powmod(_fact[_N], mod - 2);foreach_reverse (i ; 0 .. _N) {_factinv[i] = (_factinv[i+1] * (i+1)) % mod;}}long c(int n, int k) {return f(n) * finv(n - k) % _mod * finv(k) % _mod;}long p(int n, int r) {return f(n) * finv(n - r) % _mod;}long f(int n) {return _fact[n];}long finv(int n) {return _factinv[n];}long _powmod(long x, long y) {return y > 0 ? _powmod(x, y>>1)^^2 % _mod * x^^(y & 1) % _mod : 1;}}void yes(bool b) {writeln(b ? "Yes" : "No");}void YES(bool b) {writeln(b ? "YES" : "NO");}T[] readArr(T)() {return readln.split.to!(T[]);}void scan(T...)(ref T args) {import std.stdio : readln;import std.algorithm : splitter;import std.conv : to;import std.range.primitives;auto line = readln().splitter();foreach (ref arg; args) {arg = line.front.to!(typeof(arg));line.popFront();}assert(line.empty);}void fillAll(R, T)(ref R arr, T value) {static if (is(typeof(arr[] = value))) {arr[] = value;}else {foreach (ref e; arr) {fillAll(e, value);}}}