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;
	}
}