洛谷 P5520 [yLOI2019] 青原樱（组合数学 + 不互质逆元）

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

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！