专栏文章

记一种神秘线性求逆元方法

ffzs7
休闲·娱乐参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minl5zzy
此快照首次捕获于
2025/12/02 04:12
3 个月前
此快照最后确认于
2025/12/02 04:12
3 个月前
查看原文
我觉得朴素的线性求逆元方法不怎么好记，故开发了某种神秘算法来求这个东西。
我们知道，阶乘逆元是可以 O(n)O(n) 求的，设 f(i)=1i!mod  pf(i)=\frac{1}{i!} \mod p，则我们可以先求出 n!n!，然后用快速幂求出 f(n)f(n)，而我们注意到 f(i)=f(i+1)∗(i+1)f(i)=f(i+1)*(i+1)，然后阶乘逆元就 O(n)O(n) 求出来了，然后我们还发现一个东西就是 1imod  p=(i−1)!f(i)mod  p\frac{1}{i} \mod p = (i-1)!f(i) \mod p，注意到阶乘已经处理过了，直接算就行了。
代码
CPP
//_pow表阶乘,_inv表阶乘逆元,inv表逆元,V为值域,p为模数 
	_inv[0] = _pow[0] = inv[0] = 1;
	for (int i = 1; i <= V; i++) _pow[i] = _pow[i - 1] * i % p;
	_inv[V] = qpow(_pow[V]), inv[V] = _inv[V] * _pow[V - 1] % p;
	for (int i = V - 1; i >= 1; i--) _inv[i] = _inv[i + 1] * (i + 1) % p, inv[i] = _inv[i] * _pow[i - 1] % p;

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...