Submission #5738147


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 ll = long long;
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];
}

constexpr int MOD = 1000003;

mint<MOD> solve(int x, int d, ll n) {
    if (d == 0) {
        return mint<MOD>(x).pow(n);
    } else if (d == 1) {
        assert (x < MOD);
        if (x == 0) {
            return 0;
        } else if (x + n - 1 >= MOD) {
            return 0;
        } else {
            return fact<MOD>(x + n - 1) / fact<MOD>(x - 1);
        }
    } else {
        return solve((mint<MOD>(x) / d).value, 1, n) * mint<MOD>(d).pow(n);
    }
}

int main() {
    int q; cin >> q;
    while (q --) {
        int x, d; ll n; cin >> x >> d >> n;
        cout << solve(x, d, n).value << endl;
    }
    return 0;
}

Submission Info

Submission Time
Task E - Product of Arithmetic Progression
User kimiyuki
Language C++14 (GCC 5.4.1)
Score 600
Code Size 2760 Byte
Status
Exec Time 309 ms
Memory 6552 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 example0.txt
All 600 / 600 000.txt, 001.txt, 002.txt, 003.txt, 004.txt, 005.txt, 006.txt, 007.txt, 008.txt, 009.txt, 010.txt, 011.txt, 012.txt, 013.txt, 014.txt, 015.txt, 016.txt, 017.txt, 018.txt, 019.txt, example0.txt
Case Name Status Exec Time Memory
000.txt 306 ms 6256 KB
001.txt 306 ms 5616 KB
002.txt 304 ms 4976 KB
003.txt 303 ms 4720 KB
004.txt 305 ms 6256 KB
005.txt 303 ms 6512 KB
006.txt 304 ms 4720 KB
007.txt 303 ms 6128 KB
008.txt 306 ms 4848 KB
009.txt 303 ms 5744 KB
010.txt 309 ms 5616 KB
011.txt 308 ms 5744 KB
012.txt 302 ms 5872 KB
013.txt 309 ms 6000 KB
014.txt 283 ms 4848 KB
015.txt 285 ms 5744 KB
016.txt 281 ms 5360 KB
017.txt 284 ms 5488 KB
018.txt 307 ms 4592 KB
019.txt 306 ms 6552 KB
example0.txt 11 ms 6128 KB