Submission #5737909


Source Code Expand

Copy
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) begin(x), end(x)
using namespace std;

template <int32_t MOD>
struct mint {
    int32_t value;
    mint() = default;
    mint(int32_t value_) : value(value_) {}
    inline mint<MOD> operator + (mint<MOD> other) const { int32_t c = this->value + other.value; return mint<MOD>(c >= MOD ? c - MOD : c); }
    inline mint<MOD> operator - (mint<MOD> other) const { int32_t c = this->value - other.value; return mint<MOD>(c <    0 ? c + MOD : c); }
    inline mint<MOD> operator * (mint<MOD> other) const { int32_t c = (int64_t)this->value * other.value % MOD; return mint<MOD>(c < 0 ? c + MOD : c); }
    inline mint<MOD> & operator += (mint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
    inline mint<MOD> & operator -= (mint<MOD> other) { this->value -= other.value; if (this->value <    0) this->value += MOD; return *this; }
    inline mint<MOD> & operator *= (mint<MOD> other) { this->value = (int64_t)this->value * other.value % MOD; if (this->value < 0) this->value += MOD; return *this; }
    inline mint<MOD> operator - () const { return mint<MOD>(this->value ? MOD - this->value : 0); }
    mint<MOD> pow(uint64_t k) const {
        mint<MOD> x = *this, y = 1;
        for (; k; k >>= 1) {
            if (k & 1) y *= x;
            x *= x;
        }
        return y;
    }
    mint<MOD> inv() const { return pow(MOD - 2); }  // MOD must be a prime
    inline mint<MOD> operator /  (mint<MOD> other) const { return *this *  other.inv(); }
    inline mint<MOD> operator /= (mint<MOD> other)       { return *this *= other.inv(); }
};

template <int32_t MOD>
mint<MOD> fact(int n) {
    static vector<mint<MOD> > memo(1, 1);
    while (n >= memo.size()) {
        memo.push_back(memo.back() * mint<MOD>(memo.size()));
    }
    return memo[n];
}
template <int32_t PRIME>
mint<PRIME> inv_fact(int n) {
    static vector<mint<PRIME> > memo;
    if (memo.size() <= n) {
        int l = memo.size();
        int r = n * 1.3 + 100;
        memo.resize(r);
        memo[r - 1] = fact<PRIME>(r - 1).inv();
        for (int i = r - 2; i >= l; -- i) {
            memo[i] = memo[i + 1] * (i + 1);
        }
    }
    return memo[n];
}

template <int32_t MOD>
mint<MOD> choose(int n, int r) {
    assert (0 <= r and r <= n);
    return fact<MOD>(n) * inv_fact<MOD>(n - r) * inv_fact<MOD>(r);
}

constexpr int MOD = 1e9 + 7;
mint<MOD> solve(int n, int a, int b, int c) {
    mint<MOD> e = 0;
    REP (k, n) {
        mint<MOD> p1 = choose<MOD>(n + k - 1, k) * (mint<MOD>(a) / (a + b)).pow(n) * (mint<MOD>(b) / (a + b)).pow(k);
        mint<MOD> p2 = choose<MOD>(n + k - 1, k) * (mint<MOD>(a) / (a + b)).pow(k) * (mint<MOD>(b) / (a + b)).pow(n);
        mint<MOD> x = mint<MOD>(n + k) * (mint<MOD>(100) / (a + b));
        e += p1 * x;
        e += p2 * x;
    }
    return e;
}

int main() {
    int n, a, b, c; cin >> n >> a >> b >> c;
    cout << solve(n, a, b, c).value << endl;
    return 0;
}

Submission Info

Submission Time
Task C - Best-of-(2n-1)
User kimiyuki
Language C++14 (GCC 5.4.1)
Score 500
Code Size 3250 Byte
Status
Exec Time 127 ms
Memory 1912 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 example0.txt, example1.txt, example2.txt, example3.txt
All 500 / 500 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, example0.txt, example1.txt, example2.txt, example3.txt
Case Name Status Exec Time Memory
000.txt 120 ms 1912 KB
001.txt 125 ms 1912 KB
002.txt 123 ms 1912 KB
003.txt 126 ms 1912 KB
004.txt 125 ms 1912 KB
005.txt 121 ms 1912 KB
006.txt 127 ms 1912 KB
007.txt 126 ms 1912 KB
008.txt 126 ms 1912 KB
example0.txt 1 ms 256 KB
example1.txt 1 ms 256 KB
example2.txt 1 ms 256 KB
example3.txt 127 ms 1912 KB