我上一篇博客鏈接寫的是多個數求乘法逆元而快速冪求逆元用于單個數求乘法逆元

逆元是對分數取模用的

	對于除法取模不成立，即(a/b)%p≠(a%p/b%p)%p。求逆元的思路：(一般ACM的題目都是對1e9+7這種素數取模，所以gcd(a,p)==1)a*b=1(mod p) => b=1/a(mod p)。根據費馬小定理：b^(p-1)=1(mod p) => b^(p-2)=1/b(mod p)可以看出來逆元1/b (mod p)=b^(p-2)可以得出a/b對質數p取模就是 a*b^(p-2) mod p 。

2024CCPC鄭州邀請賽-Problem H. 隨機棧用到了逆元但當時沒有想到沒有寫出來

代碼如下

#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
# define int long long
using namespace std;
int mod = 998244353;
map<int, int> m;
int asd(int a, int b) 
{int sum = 1;while(b){if(b%2==0){a=a*a%mod;b=b/2;}else{b=b-1;sum=sum*a%mod;b=b/2;a=a*a%mod;}}return sum%mod;
}
signed  main() {priority_queue<int, vector<int>, greater<int> > p;int n, num, l = -1, t = 0, s = 1, x = 1;cin >> n;for (int i = 0; i < 2 * n; i++) {cin >> num;if (t != 1){if (num == -1) {s = s * m[p.top()] % mod;x = x * p.size() % mod;if (p.top() >= l) {l = p.top();m[p.top()]--;p.pop();}elset = 1;} else {p.push(num);m[num]++;}}}if (t == 1)cout << "0" << endl;else {int ans = s * asd(x, mod - 2) % mod;cout << ans << endl;}}