結果
問題 | No.940 ワープ ε=ε=ε=ε=ε=│;p>д<│ |
ユーザー | jell |
提出日時 | 2020-01-18 20:17:36 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 622 ms / 5,000 ms |
コード長 | 7,671 bytes |
コンパイル時間 | 714 ms |
コンパイル使用メモリ | 75,424 KB |
実行使用メモリ | 44,376 KB |
最終ジャッジ日時 | 2024-06-28 02:35:04 |
合計ジャッジ時間 | 5,477 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 5 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 3 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 3 ms
6,940 KB |
testcase_08 | AC | 2 ms
6,944 KB |
testcase_09 | AC | 3 ms
6,944 KB |
testcase_10 | AC | 2 ms
6,944 KB |
testcase_11 | AC | 2 ms
6,940 KB |
testcase_12 | AC | 3 ms
6,944 KB |
testcase_13 | AC | 3 ms
6,940 KB |
testcase_14 | AC | 2 ms
6,940 KB |
testcase_15 | AC | 39 ms
6,944 KB |
testcase_16 | AC | 118 ms
7,504 KB |
testcase_17 | AC | 294 ms
24,032 KB |
testcase_18 | AC | 344 ms
24,028 KB |
testcase_19 | AC | 289 ms
23,896 KB |
testcase_20 | AC | 416 ms
23,904 KB |
testcase_21 | AC | 174 ms
13,660 KB |
testcase_22 | AC | 401 ms
23,896 KB |
testcase_23 | AC | 138 ms
9,552 KB |
testcase_24 | AC | 408 ms
24,024 KB |
testcase_25 | AC | 533 ms
27,884 KB |
testcase_26 | AC | 622 ms
44,376 KB |
コンパイルメッセージ
main.cpp:157:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 157 | main() | ^~~~
ソースコード
#ifndef Modint_runtime_hpp #define Modint_runtime_hpp #include <cassert> #include <iostream> // modulo statically fixed class modint_runtime { long long val; friend std::ostream &operator<<(std::ostream &os, const modint_runtime &other) noexcept { return os << other.val; } friend std::istream &operator>>(std::istream &is, modint_runtime &other) noexcept { long long val; other = modint_runtime((is >> val, val)); return is; } public: static long long &mod() noexcept { static long long mod{}; return mod; } modint_runtime(long long x = 0) : val{(x %= mod()) < 0 ? x + mod() : x} {} long long value() const noexcept { return val; } modint_runtime operator++(int) noexcept { modint_runtime t = *this; return ++val, t; } modint_runtime &operator++() noexcept { return ++val, *this; } modint_runtime operator--(int) noexcept { modint_runtime t = *this; return --val, t; } modint_runtime &operator--() noexcept { return --val, *this; } modint_runtime &operator=(long long other) noexcept { return val = (other %= mod()) < 0 ? other + mod() : other, *this; } modint_runtime &operator+=(long long other) noexcept { return (val += other % mod()) < mod() ? 0 : val -= mod(), *this; } modint_runtime &operator+=(const modint_runtime &other) noexcept { return (val += other.val) < mod() ? 0 : val -= mod(), *this; } modint_runtime &operator-=(long long other) noexcept { return (val += mod() - other % mod()) < mod() ? 0 : val -= mod(), *this; } modint_runtime &operator-=(const modint_runtime &other) noexcept { return (val += mod() - other.val) < mod() ? 0 : val -= mod(), *this; } modint_runtime &operator*=(long long other) noexcept { return (val *= other % mod()) %= mod(), *this; } modint_runtime &operator*=(const modint_runtime &other) noexcept { return (val *= other.val) %= mod(), *this; } modint_runtime &operator/=(long long other) noexcept { return *this *= inverse(other); } modint_runtime &operator/=(const modint_runtime &other) noexcept { return *this *= inverse(other); } modint_runtime operator-() const noexcept { return modint_runtime(-val); } modint_runtime operator+(const modint_runtime &other) const noexcept { return modint_runtime{*this} += other; } modint_runtime operator-(const modint_runtime &other) const noexcept { return modint_runtime{*this} -= other; } modint_runtime operator*(const modint_runtime &other) const noexcept { return modint_runtime{*this} *= other; } modint_runtime operator/(const modint_runtime &other) const noexcept { return modint_runtime{*this} /= other; } bool operator==(const modint_runtime &other) const noexcept { return val == other.val; } bool operator!=(const modint_runtime &other) const noexcept { return val != other.val; } bool operator!() const noexcept { return !val; } friend modint_runtime operator+(long long x, modint_runtime y) noexcept { return {x + y.val}; } friend modint_runtime operator-(long long x, modint_runtime y) noexcept { return {x - y.val}; } friend modint_runtime operator*(long long x, modint_runtime y) noexcept { return {x % mod() * y.val}; } friend modint_runtime operator/(long long x, modint_runtime y) noexcept { return {x % mod() * inverse(y).val}; } static modint_runtime inverse(const modint_runtime &other) noexcept { assert(mod() && other.val); long long a{mod()}, b{other.val}, u{}, v{1}, t{}; while(b) t = a / b, a ^= b ^= (a -= t * b) ^= b, u ^= v ^= (u -= t * v) ^= v; return {u}; } static modint_runtime pow(modint_runtime other, long long e) noexcept { if(e < 0) e = e % (mod() - 1) + mod() - 1; modint_runtime res{1}; while(e) { if(e & 1) res *= other; other *= other, e >>= 1; } return res; } }; // class modint_runtime #endif #ifndef Factorial_runtime_hpp #define Factorial_runtime_hpp #include <vector> class factorial_runtime { const int mod; int n; std::vector<int> fact; public: factorial_runtime(int _mod) : mod{_mod}, n{1}, fact{1} {} int modulo() const { return mod; } void reserve(int m) { if(m < n) return; m = 1 << (32 - __builtin_clz(m)); fact.resize(m); for(int i = n; i < m; ++i) fact[i] = (long long)fact[i - 1] * i % mod; n = m; } // modint_runtime operator()(const int x) noexcept { reserve(x); return {x < 0 ? 0 : fact[x], mod}; } modint_runtime operator()(const int x) noexcept { reserve(x); return {x < 0 ? 0 : fact[x]}; } }; #endif #ifndef Inverse_runtime_hpp #define Inverse_runtime_hpp #include <vector> class inverse_runtime { const int mod; int n; std::vector<int> inv; public: inverse_runtime(int _mod) : mod{_mod}, n{2}, inv{0, 1} {} int modulo() const { return mod; } void reserve(int m) { if(m < n) return; m = 1 << (32 - __builtin_clz(m)); inv.resize(m); for(int i = n; i < m; ++i) inv[i] = mod - (long long)mod / i * inv[mod % i] % mod; n = m; } // modint_runtime operator()(const int x) noexcept { assert(x), reserve(x); return {inv[x], mod}; } modint_runtime operator()(const int x) noexcept { assert(x), reserve(x); return {inv[x]}; } }; #endif // Inverse_runtime_hpp #ifndef Inverse_factorial_runtime_hpp #define Inverse_factorial_runtime_hpp #include <vector> class inverse_factorial_runtime { inverse_runtime &inv_gen; const int mod; int n; std::vector<int> inv_fact; public: inverse_factorial_runtime(inverse_runtime &_inv_gen) : inv_gen{_inv_gen}, mod{_inv_gen.modulo()}, n{1}, inv_fact{1} {} int modulo() const { return mod; } void reserve(int m) { if(m < n) return; m = 1 << (32 - __builtin_clz(m)); inv_fact.resize(m); for(int i = n; i < m; ++i) inv_fact[i] = inv_fact[i - 1] * inv_gen(i).value() % mod; n = m; } // modint_runtime operator()(const int x) noexcept { reserve(x); return {x < 0 ? 0 : inv_fact[x], mod}; } modint_runtime operator()(const int x) noexcept { reserve(x); return {x < 0 ? 0 : inv_fact[x]}; } }; #endif // Inverse_factorial_runtime_hpp #ifndef Binomial_runtime_hpp #define Binomial_runtime_hpp #include <vector> class binomial_runtime { factorial_runtime &fact_gen; inverse_factorial_runtime &inv_fact_gen; const int mod; public: binomial_runtime(factorial_runtime &_fact_gen, inverse_factorial_runtime &_inv_fact_gen) : fact_gen(_fact_gen), inv_fact_gen(_inv_fact_gen), mod{_fact_gen.modulo()} {} int modulo() const { return mod; } void reserve(const int m) noexcept { fact_gen.reserve(m); inv_fact_gen.reserve(m); } modint_runtime operator()(const int x, const int y) noexcept { return fact_gen(x) * inv_fact_gen(y) * inv_fact_gen(x - y); } }; #endif using namespace std; main() { const int mod=1e9+7; using mint=modint_runtime; mint::mod()=mod; factorial_runtime fac(mod); inverse_runtime inv(mod); inverse_factorial_runtime ifac(inv); binomial_runtime binom(fac,ifac); // binom.reserve(2200000); int x,y,z; cin>>x>>y>>z; // mint ans{0,mod},s{1,mod}; mint ans{0},s{1}; for(int k=x+y+z,f=1; k>=0; --k,f^=1) { mint tmp=s; if(x) { tmp*=binom(x+k-1,k-1); } if(y) { tmp*=binom(y+k-1,k-1); } if(z) { tmp*=binom(z+k-1,k-1); } ans+=tmp; s*=2; if(f) { s-=binom(x+y+z+1,k); } else { s+=binom(x+y+z+1,k); } } cout << ans << "\n"; return 0; }