首页 > 代码库 > 为什么组合数取模要用逆元

为什么组合数取模要用逆元

首先说明一个事实,你直接算出来一个组合数的结果直接对p取模,结果一定是对的,那么这是对一个计算结果一次取模

(但上面的前提是你使用的数据结构能存储得下取模前的结果

但如果我们要通过一个前面取过模的式子递推出其他要取模的式子,而递推式里又存在除法

那么一个很尴尬的事情出现了,假如a[i-1]=100%31=7 a[i]=(a[i-1]/2)%31

a[i]=50%31=19 ,但我们现在只知道a[i-1]=7,如何计算出a[i]=19呢? a[i]=(7/2)%31=3?

其实本来是100是整除2的,但是对31取模后就不能整除了,所以我们要求出在mod 31意义下2的逆元是多少

口算可得,2*16%31=1,所以2的逆元就是16,所以a[i]=(a[i-1]*inv(2))%31=7*16%31=19

那么通过逆元我们就得到了正确的结果

为什么组合数取模要用逆元