Submission #1684212
Source Code Expand
#if 1 #include <iostream> #include <fstream> #include <string> #include <vector> #include <map> #include <set> #include <unordered_map> #include <unordered_set> #include <queue> #include <stack> #include <array> #include <deque> #include <algorithm> #include <utility> #include <cstdint> #include <functional> #include <iomanip> #include <numeric> #include <assert.h> #include <bitset> auto& in = std::cin; auto& out = std::cout; template<typename Arithmetic, typename Integral> std::enable_if_t< std::is_unsigned<Integral>::value, Arithmetic> ipow(Arithmetic bace, Integral n) { //繰り返し二条法 auto res = (Arithmetic)(1); while (n > 0) { if (n & 1) res *= bace; bace *= bace; n >>= 1; } return res; } constexpr bool is_prime(uint32_t N) { if (N <= 1) { return false; } for (size_t i = 2; i*i <= N; ++i) { if (N%i == 0) { return false; } } return true; } template <uint64_t MOD> class mint_base; //mint_base_base型用の累乗関数 template <uint64_t MOD> constexpr mint_base<MOD> m_pow(mint_base<MOD> x, uint64_t n)noexcept; //mod計算を自動で行う整数テンプレートクラス template <uint64_t MOD_ = 1000000007> class mint_base { public: static constexpr auto MOD = MOD_; static_assert(!(MOD <= 2), "MOD cannot be below 2."); static_assert(MOD <= (0xFFFFFFFFFFFFFFFF / 2), "MOD is too big");//加算してオーバーフローしない static_assert(MOD <= 0xFFFFFFFF, "MOD is too big");//乗算してオーバーフローしない constexpr mint_base<MOD> operator+(const mint_base<MOD> &other)const noexcept { auto v = *this; return v += other; } constexpr mint_base<MOD> operator-(const mint_base<MOD> &other)const noexcept { auto v = *this; return v -= other; } constexpr mint_base<MOD> operator*(const mint_base<MOD> &other)const noexcept { auto v = *this; return v *= other; } constexpr auto operator/(const mint_base<MOD> &other)const noexcept { auto v = *this; return v /= other; } constexpr mint_base<MOD>& operator+=(const mint_base<MOD> &other) noexcept { a += other.a; if (MOD <= a) { a -= MOD; }; return *this; } constexpr mint_base<MOD>& operator-=(const mint_base<MOD> &other) noexcept { if (a >= other.a) { a -= other.a; } else { a = (a + MOD) - other.a; } return *this; } constexpr mint_base<MOD>& operator*=(const mint_base<MOD> &other) noexcept { #if 1 a *= other.a; a %= MOD; #else //MOD <= (MAXUINT64 / 2)条件下 uint64_t b = other.a, v = 0; while (b > 0) { if (b & 1) { v += a; if (v >= MOD)v -= MOD; } a += a; if (MOD <= a)a -= MOD; b >>= 1; } a = v; #endif return *this; } constexpr mint_base<MOD>& operator/=(const mint_base<MOD> &other) noexcept { return *this *= ~other; } constexpr mint_base<MOD> operator+()const noexcept { return *this; } constexpr mint_base<MOD> operator-()const noexcept { return{ MOD - a, mod_value_tag{} }; } constexpr mint_base<MOD>& operator++() noexcept { if (MOD <= ++a) { a = 0; }; return *this; } constexpr mint_base<MOD>& operator--() noexcept { if (a <= 0) { a = MOD; }; --a; return *this; } constexpr mint_base<MOD> operator++(int) noexcept { auto tmp = *this; ++*this; return tmp; } constexpr mint_base<MOD> operator--(int) noexcept { auto tmp = *this; --*this; return tmp; } constexpr mint_base<MOD> operator~()const noexcept { return ipow(*this, e_phi - 1); } constexpr mint_base<MOD>& operator=(const mint_base<MOD> &other) noexcept { a = other.a; return *this; } constexpr explicit operator uint64_t()const noexcept { return a; } constexpr explicit operator unsigned()const noexcept { return (unsigned)a; } static constexpr uint64_t getmod() noexcept { return MOD; } constexpr mint_base(uint64_t a_) noexcept :a(a_ % MOD) {} constexpr mint_base()noexcept : a(0) {} struct mod_value_tag {}; constexpr mint_base(uint64_t a_, mod_value_tag) :a(a_) {} private: static constexpr uint64_t get_e_phi()noexcept { //オイラー値の導出 uint64_t temp = MOD; uint64_t m_ = MOD; for (uint64_t i = 2; i * i <= m_; ++i) { if (m_ % i == 0) { temp = temp / i * (i - 1); for (; m_ % i == 0; m_ /= i); } } if (m_ != 1)temp = temp / m_ * (m_ - 1); return temp; } static constexpr uint64_t e_phi = get_e_phi();//オイラー値 uint64_t a; }; //mint_base型用の累乗関数 template<uint64_t MOD>constexpr mint_base<MOD> m_pow(mint_base<MOD> x, uint64_t n)noexcept { mint_base<MOD> res = 1; while (n > 0) { if (n & 1)res *= x; x *= x; n >>= 1; } return res; } //mint_baseの階乗計算 //O(x)時間が必要のため、fact_set関数を推奨する。 template<uint64_t MOD>constexpr mint_base<MOD> fact(mint_base<MOD> x)noexcept { mint_base<MOD> res(1); for (uint64_t i = 1; i <= (uint64_t)x; ++i) { res *= i; } return res; } //mint_baseの階乗計算 //0からxまでの階乗を返す //O(x)時間が必要 template<uint64_t MOD>std::vector<mint_base<MOD>> fact_set(mint_base<MOD> x = mint_base<MOD>(-1)) { mint_base<MOD> res(1); std::vector<mint_base<MOD>> set((uint64_t)(x)+1); set[0] = 1; for (uint64_t i = 1; i <= (uint64_t)x; ++i) { res *= i; set[i] = res; } return res; } //mint_base型のstreamへの出力 template<uint64_t MOD> std::ostream& operator<<(std::ostream& os, mint_base<MOD> i) { os << (uint64_t)i; return os; } //mint_base型のstreamからの入力 template<uint64_t MOD> std::istream& operator >> (std::istream& is, mint_base<MOD>& i) { uint64_t tmp; is >> tmp; i = tmp; return is; } typedef mint_base<1000000007> mint; namespace mint_literal { constexpr mint operator""_mi(unsigned long long x)noexcept { return mint(x); } } using namespace mint_literal; //mint_baseの階乗計算 //0からxまでの階乗を返す //O(N) template<int32_t X, uint64_t MOD = mint::MOD> /*constexpr*/ std::array<mint_base<MOD>, X + 1> fact_set_c() { mint_base<MOD> res(1); std::array<mint_base<MOD>, X + 1> set; set[0] = 1; for (int32_t i = 1; i <= X; ++i) { res *= i; set[i] = res; } return set; } template<typename RET = mint, typename Integral> RET combination(Integral all, Integral get) { assert(all >= get); get = std::min(all - get, get); #if 1 //時間計算量O(logMOD) static const auto fact_v = fact_set_c<100001>(); return fact_v[all] / (fact_v[get] * fact_v[all - get]); #elif 0 //時間計算量O(1) //空間計算量、初期化時間計算量O(N^2) constexpr int32_t ALL_MAX = 10'000; static std::vector<RET> DP_comb[ALL_MAX + 1]; if (!DP_comb[all].empty()) { return DP_comb[all][get]; } if (DP_comb[0].empty()) { DP_comb[0].resize(1); DP_comb[0][0] = (RET)1; DP_comb[1].resize(1); DP_comb[1][0] = (RET)1; } for (int32_t i = 2; i <= all; i++) { if (DP_comb[i].empty()) { int32_t size = i / 2 + 1; DP_comb[i].resize(size); DP_comb[i][0] = (RET)1; for (int32_t j = 1; j < size - 1; j++) { DP_comb[i][j] = DP_comb[i - 1][j - 1] + DP_comb[i - 1][j]; } DP_comb[i][size - 1] = DP_comb[i - 1][size - 2] + DP_comb[i - 1][(i & 1) ? (size - 1) : (size - 2)]; } } return DP_comb[all][get]; #else //時間計算量O(get * logMOD) RET ret = (RET)1; for (Integral i = 1; i <= get; ++i) { ret *= all + 1 - i; ret /= i; } return ret; #endif } mint a, u, r; int main() { using std::endl; in.sync_with_stdio(false); out.sync_with_stdio(false); in.tie(nullptr); out.tie(nullptr); in >> a>>u>>r; mint D = u - a,E=r-a; out << (r*D) / ((u + r)*a - u*r) <<' ' <<(u*E) / ((u + r)*a - u*r) << endl; // a*(1+ y/(x+1)) = r //<=>a * (x + y + 1) = r*(x+1) //<=>a * y = (r-a)*(x+1) //a*(1+ x/(y+1)) = u //<=>a * (x + y + 1) = u*(y+1) //<=>a * (y + (a * y)/(r-a)) = u*(y+1) //<=>a * (r * y)/(r-a) = u*(y+1) return 0; } #endif
Submission Info
Submission Time | |
---|---|
Task | D - 動的計画法 |
User | eiya |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 8145 Byte |
Status | AC |
Exec Time | 1 ms |
Memory | 256 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 100 / 100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | sample_01.txt, sample_02.txt, sample_03.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt, subtask2_29.txt, subtask2_30.txt, subtask2_31.txt, subtask2_32.txt, subtask2_33.txt, subtask2_34.txt, subtask2_35.txt, subtask2_36.txt, subtask2_37.txt, subtask2_38.txt, subtask2_39.txt, subtask2_40.txt, subtask2_41.txt, subtask2_42.txt, subtask2_43.txt, subtask2_44.txt, subtask2_45.txt, subtask2_46.txt, subtask2_47.txt, subtask2_48.txt, subtask2_49.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 1 ms | 256 KB |
sample_02.txt | AC | 1 ms | 256 KB |
sample_03.txt | AC | 1 ms | 256 KB |
subtask2_01.txt | AC | 1 ms | 256 KB |
subtask2_02.txt | AC | 1 ms | 256 KB |
subtask2_03.txt | AC | 1 ms | 256 KB |
subtask2_04.txt | AC | 1 ms | 256 KB |
subtask2_05.txt | AC | 1 ms | 256 KB |
subtask2_06.txt | AC | 1 ms | 256 KB |
subtask2_07.txt | AC | 1 ms | 256 KB |
subtask2_08.txt | AC | 1 ms | 256 KB |
subtask2_09.txt | AC | 1 ms | 256 KB |
subtask2_10.txt | AC | 1 ms | 256 KB |
subtask2_11.txt | AC | 1 ms | 256 KB |
subtask2_12.txt | AC | 1 ms | 256 KB |
subtask2_13.txt | AC | 1 ms | 256 KB |
subtask2_14.txt | AC | 1 ms | 256 KB |
subtask2_15.txt | AC | 1 ms | 256 KB |
subtask2_16.txt | AC | 1 ms | 256 KB |
subtask2_17.txt | AC | 1 ms | 256 KB |
subtask2_18.txt | AC | 1 ms | 256 KB |
subtask2_19.txt | AC | 1 ms | 256 KB |
subtask2_20.txt | AC | 1 ms | 256 KB |
subtask2_21.txt | AC | 1 ms | 256 KB |
subtask2_22.txt | AC | 1 ms | 256 KB |
subtask2_23.txt | AC | 1 ms | 256 KB |
subtask2_24.txt | AC | 1 ms | 256 KB |
subtask2_25.txt | AC | 1 ms | 256 KB |
subtask2_26.txt | AC | 1 ms | 256 KB |
subtask2_27.txt | AC | 1 ms | 256 KB |
subtask2_28.txt | AC | 1 ms | 256 KB |
subtask2_29.txt | AC | 1 ms | 256 KB |
subtask2_30.txt | AC | 1 ms | 256 KB |
subtask2_31.txt | AC | 1 ms | 256 KB |
subtask2_32.txt | AC | 1 ms | 256 KB |
subtask2_33.txt | AC | 1 ms | 256 KB |
subtask2_34.txt | AC | 1 ms | 256 KB |
subtask2_35.txt | AC | 1 ms | 256 KB |
subtask2_36.txt | AC | 1 ms | 256 KB |
subtask2_37.txt | AC | 1 ms | 256 KB |
subtask2_38.txt | AC | 1 ms | 256 KB |
subtask2_39.txt | AC | 1 ms | 256 KB |
subtask2_40.txt | AC | 1 ms | 256 KB |
subtask2_41.txt | AC | 1 ms | 256 KB |
subtask2_42.txt | AC | 1 ms | 256 KB |
subtask2_43.txt | AC | 1 ms | 256 KB |
subtask2_44.txt | AC | 1 ms | 256 KB |
subtask2_45.txt | AC | 1 ms | 256 KB |
subtask2_46.txt | AC | 1 ms | 256 KB |
subtask2_47.txt | AC | 1 ms | 256 KB |
subtask2_48.txt | AC | 1 ms | 256 KB |
subtask2_49.txt | AC | 1 ms | 256 KB |