s://.luogu.com.cn/problem/P5520 我组合数学也太菜了吧，这题思路相当简单。第一种想法是：m个树占m个位置，然后拿m – 1个位置填在m个树之间，然后就是一个n – 2 * m + 1个球放m + 1个盒子里，盒子可以为空的放法数了，结果就是 C n – m + 1 m C_{n – m + 1}^{m} Cn–m+1m。另一种思路更简单，就是先抽出m – 1个位置出来，然后剩下的位置里选m个，直接就是 C n – m + 1 m C_{n – m + 1}^{m} Cn–m+1m种了，然后把这m – 1个位置插在两两之间可以保证一定没有相邻的，太强了。 然后还有个问题就是这题的p不一定是质数也不一定互质，然后我看到了一种求(a/b)%c的方法:(其中b|a)，先求k=gcd(b,c)，然后求b/k的逆元p，接着计算 ( a ∗ p ) m o d c k \frac{(a*p)\ mod\ c}{k} k(a∗p) mod c即为答案，目前还不知道原理以后再看看吧。s://.luogu.com.cn/discuss/show/143253。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e6 + 10; ll fac[maxn], mod; ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a % b);} ll x, y; void extgcd(ll a, ll b, ll &x, ll &y) { if (b == 0) x = 1, y = 0; else{ extgcd(b, a % b, y, x); y -= (a / b) * x; } } ll C(int n, int m) { ll k = gcd(fac[m] * fac[n - m], mod); extgcd(fac[m] * fac[n - m] / k, mod / k, x, y); if (x < 0) x += mod / k; return fac[n] * x % mod / k; } int main() { int t, n, m; cin >> t >> n >> m >> mod; fac[0] = fac[1] = 1; for (int i = 2; i < maxn; ++i) fac[i] = (i * fac[i - 1]) % mod; cout << C(n - m + 1, m) * fac[m] % mod << endl; return 0; }