M-SOLUTIONS プロコンオープン E - Product of Arithmetic Progression

最近作った剰余演算用のライブラリを試すのにうってつけの問題。

nCmは使わないけど、累乗や逆数、そしておまけで作ったnPmの計算を使っています。

計算自体はよくある手法だと思うけど、配列をコンストラクタの中で初期化するので

サンプルごとにメモリの使用量が変化するのが見ていて楽しいです。

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define rep(i, n) for (int i = 0; i < (n); i++)

#define repf(i, j, n) for (int i = (j); i < (n); i++)

#define repr(i, n) for (int i = (n)-1; i >= 0; i--)

struct modCalc {

int mod;

int n;

vector<int> fact, invfact;

modCalc(){};

modCalc(int _mod, int _n) {

mod = _mod, n = _n;

fact.resize(n + 1, 1);

invfact.resize(n + 1, 1);

for (int i = 0; i < n; i++) fact[i + 1] = fact[i] * (i + 1) % mod;

invfact[n] = modinv(fact[n]);

for (int i = n; i > 1; i--) invfact[i - 1] = invfact[i] * i % mod;

};

int modpow(int x, int n) {

int ret = 1;

while (n > 0) {

if (n & 1) (ret *= x) %= mod;

(x *= x) %= mod;

n >>= 1;

}

return ret;

}

int modinv(int x) { return modpow(x, mod - 2); }

int nCm(int x, int y) {

if (y == 0)

return 1;

else

return fact[x] * invfact[y] % mod * invfact[x - y] % mod;

}

int nPm(int x, int y ) {

return fact[x] * invfact[x - y] % mod;

}

};

signed main() {

int q;

cin >> q;

vector<int> x(q), d(q), n(q);

rep(i, q) cin >> x[i] >> d[i] >> n[i];

int mod = 1e6 + 3;

modCalc mc(mod, mod - 1);

rep(i, q) {

int x0 = x[i], d0 = d[i], n0 = n[i];

if (x0 == 0) {

cout << 0 << endl;

continue;

}

if (d0 == 0) {

cout << mc.modpow(x0, n0) << endl;

continue;

}

int dn = mc.modpow(d0, n0);

int xd = mc.modinv(d0) * x0 % mod;

if (xd + n0 - 1 >= mod) {

cout << 0 << endl;

continue;

}

int ret = mc.nPm(xd + n0 - 1, n0) * dn % mod;

cout << ret << endl;

}

}