Vexoben
Jan 31, 2019
在一次比赛中因为不会线性处理一段区间的逆元被卡了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\)的递推式。
\[S_k=\frac{\sum_{x=1}^{n}T^x\dbinom{n-x}{k-1}}{\dbinom{n}{k}}\] \[TS_k=\frac{\sum_{x=2}^{n+1}T^x\dbinom{n-x+1}{k-1}}{\dbinom{n}{k}}\] \[(T-1)S_k=\frac{\sum_{x=2}^{n}T^x\dbinom{n-x}{k-2}-T\dbinom{n-1}{k-1}}{\dbinom{n}{k}}\] \[(T-1)\dbinom{n}{k}S_k=\dbinom{n}{k-1}(S_{k-1}-T)\] \[(T-1)S_k= \frac{k}{n-k+1}(S_{k-1}-T)\]预处理\(n-k\)到\(n\)的逆元之后递推即可。