S2OJ - 631. 故事书

#题面

#题目背景

她是清晨告别洋流启程的沙砾

同忽闪漂流瓶将白日梦唤醒

好奇目光激发导带微弱的磁极

从此把全世界吸引

她看故事书无聊将那零和一堆砌

牛郎还不解混沌距离外浪迹的织女星

注脚总文不对题字里行间全是歪理

只是也总祈望光线彼端未歇的繁星

#题目描述

一本「故事书」上写了下面的算式:

$$\left( \prod_{i=0}^{n-1} {(a + i \times d)} \right) \pmod p$$

给定质数 $p$，$T$ 次询问非负整数 $a, d, n$, 求上式的值。

#输入格式

第一行，两个正整数 $T, p$。

之后 $T$ 行，每行三个非负整数 $a, d, n$, 表示一组询问。

#输出格式

$T$ 行，每行一个非负整数，表示询问的答案。

#输入输出样例

样例输入 #1

2 1000003
7 2 4
12345 67890 2019

样例输出 #1

9009
916936

#数据范围与约定

对于所有数据, $p$ 是质数, $a, d \lt p, n \leq 10^9$。

#思路

$$\begin{aligned} & \prod_{i = 0}^{n - 1} \left( a + i \times d \right) \\ =& \prod_{i = 0}^{n - 1} \left( \frac{a}{d} + i \right) \times d \\ =& d^n \times \prod_{i = 0}^{n - 1} \left( \frac{a}{d} + i \right) \\ \end{aligned}$$

显然当 $d = 0$ 时，答案为 $a^n \bmod p$。那么考虑如何在 $d > 0$ 的情况下求出 $\displaystyle \prod_{i = 0}^{n - 1} \left( \frac{a}{d} + i \right)$。

将 $\displaystyle \prod_{i = 0}^{n - 1} \left( \frac{a}{d} + i \right)$ 展开，可得：

$$\begin{aligned} & \prod_{i = 0}^{n - 1} \left( \frac{a}{d} + i \right) \\ =& (\frac{a}{d} + 0) + (\frac{a}{d} + 1) + (\frac{a}{d} + 2) + \cdots + (\frac{a}{d} + n - 1) \\ \end{aligned}$$

在每一项中都出现了 $\dfrac{a}{d}$，那么可以通过在前面补齐 $1 \sim \dfrac{a}{d} - 1$ 再将其约分掉的办法来简化该式的计算：

$$\begin{aligned} & \frac{a}{d} + (\frac{a}{d} + 1) + (\frac{a}{d} + 2) + \cdots + (\frac{a}{d} + n - 1) \\ =& \frac{1 + 2 + \cdots + (\frac{a}{d} - 1) + \frac{a}{d} + (\frac{a}{d} + 1) + (\frac{a}{d} + 2) + \cdots + (\frac{a}{d} + n - 1)}{1 + 2 + \cdots + (\frac{a}{d} - 1)} \\ =& \frac{(\frac{a}{d} + n - 1)!}{(\frac{a}{d} - 1)!} \end{aligned}$$

最后别忘了求出来的答案还要乘上 $d^n$。

特别地，在阶乘时，如果某一项的值恰好 $= p$，那么整个式子的值就会变成 $0$，所以可以特判一下来优化运行时间。

#代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

#include <iostream>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 1e7 + 5;

int t, p, a, d, n;
int fac[N], inv[N], fac_inv[N];

constexpr int binpow(int a, int b, int mod) {
    int res = 1;
    a %= mod;

    while (b) {
        if (b & 1) res = static_cast<long long>(res) * a % mod;
        a = static_cast<long long>(a) * a % mod;
        b >>= 1;
    }

    return res;
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> t >> p;

    fac[0] = 1;
    for (int i = 1; i <= p; i++) {
        fac[i] = static_cast<long long>(fac[i - 1]) * i % p;
    }

    inv[0] = inv[1] = 1;
    for (int i = 2; i <= p; i++) {
        inv[i] = static_cast<long long>(p - (p / i)) * inv[p % i] % p;
    }

    fac_inv[0] = fac_inv[1] = 1;
    for (int i = 2; i <= p; i++) {
        fac_inv[i] = static_cast<long long>(fac_inv[i - 1]) * inv[i] % p;
    }

    while (t--) {
        cin >> a >> d >> n;

        if (d == 0) {
            cout << binpow(a, n, p) << endl;
        } else {
            int k = static_cast<long long>(a) * inv[d] % p;

            if (k == 0 || n + k - 1 > p) {
                cout << 0 << endl;
            } else {
                cout << static_cast<long long>(fac[n + k - 1]) * fac_inv[k - 1] % p * binpow(d, n, p) % p << endl;
            }
        }
    }

    return 0;
}