线性处理一段区间的逆元

在一次比赛中因为不会线性处理一段区间的逆元被卡了52分.这里记下这个问题的解法.

(刷新以获取数学公式)

线性处理$[1,n]$的逆元

inv[1] = 1;
for (int i = 2; i <= n; ++i) {
	 inv[i] = -mod / i * inv[mod % i] % mod + mod;
}

线性处理任意区间的逆元

上面一种方法不易扩展到任意区间,我们可以扩展线性处理逆元的另一种方法:

假设我们要处理区间$[l,r]$在模$mod$意义下的逆元,可以先求出$fac_x=\prod_{l≤i≤x}i和fav_x=fac_x^{-1}$, 那么$inv_x=fav_x*fac_{x-1}$

计算$fav$的时候,先由费马小定理计算出$fav_{r}$,然后用$fav_x=fav_{x+1}*(x+1)$递推即可.

一道例题

题意

计算 $\frac{\sum_{x=1}^{n}T^x\dbinom{n-x}{k-1}}{\dbinom{n}{k}}$

数据范围：$1≤k≤n≤1e9,k≤1e7,T≤998244352$, 答案模$998244353$输出

题解

由数据范围可以想到关键是将和式转化为关于$k$的递推式。

预处理$n-k$到$n$的逆元之后递推即可。