OiClass PUJI P3827 函数 题解

思路

首先化简一下公式： \[ \begin{align*} f(n,\,r)&={\rm C}^r_n (n - r)!\\ &=\frac{A^r_n(n - r)!}{r!}\\ &=\frac{n!}{r!}\\ &=\prod _{i=r + 1}^n i \end{align*} \] 但是数据范围很大，于是我们考虑使用数据结构来优化这个查询。第一感觉是 ST 表，结果发现预处理和查询都会遇到除法，这就会导致你需要使用逆元，能不能卡过去切不好说，代码难度已经很高了。

于是我们使用众所周知的线段树来解决区间查询的问题，就十分简单了，简单建一下树然后直接查询就可以了，根本不用修改之类的操作，十分简单。就是需要注意一下开 __int128，要不然计算的过程中会爆 long long，大寄。

代码

#include <iostream>

#define int long long
#define endl '\n'

using namespace std;

int q, mod, n, r;
__int128 tree[400009];

void build(const int node, const int l, const int r) {
    if (l == r) {
        tree[node] = l;
        return;
    }
    int mid = (l + r) >> 1;
    build(node << 1, l, mid);
    build(node << 1 | 1, mid + 1, r);
    tree[node] = (tree[node << 1] * tree[node << 1 | 1]) % mod;
}

__int128 query(const int node, int l, int r, const int L, const int R) {
    if (L <= l && r <= R) {
        return tree[node];
    }
    int mid = (l + r) >> 1;
    __int128 ans = 1;
    if (L <= mid) {
        ans *= query(node << 1, l, mid, L, R);
        ans %= mod;
    }
    if (R > mid) {
        ans *= query(node << 1 | 1, mid + 1, r, L, R);
        ans %= mod;
    }
    return ans;
}

signed main() {
    cin >> q >> mod;
    build(1, 1, 100000);
    while (q--) {
        cin >> n >> r;
        cout << (int) query(1, 1, 100000, r + 1, n) << endl;
    }
}