P5431 【【模板】乘法逆元2】
2024-09-07 05:13:38
卡常毒瘤题。交了一页的我。
首先容易想出暴力的做法,直接逆元累加,复杂度\(O(nlogn)\)。
for(register int i=1;i<=n;++i){
ll a=read();
ans=(ans%p+qp(k,i)*qp(a,p-2)%p)%p;
}
我第一次交就直接这样子,憨憨,连\(k\)都不优化一下。
作为一道毒瘤题,她(指鱼鱼)怎么可能这么简单地就让你过了呢(详见讨论)??
我们需要寻找线性复杂度算法。
首先考虑为什么渐进复杂度里有个\(log\),是因为每次累加我们都\(O(logn)\)地求了逆元。
换个思路,如果我们把所求式子都通分,先把分子乘起来,最后再乘上\(\sum_{i=1}^na_i \pmod p\)的逆元,不就不用除那么多次了吗。
设\(s=\sum_{i=1}^na_i\),则有
\[\sum\limits_{i=1}^n\frac{k^i}{a_i}=\sum_{i=1}^n\frac{k^i*(\frac{s}{a_i})}{s}
\]
\]
但是分子又出现了除法,如果直接求逆元又退化到了\(O(nlogn)\)。考虑维护\(a\)的前缀、后缀积\(h[],t[]\),那么\(\frac{s}{a_i}=h[i-1]*t[i+1]\)。预处理之后即可线性求解。
for(register int i=1;i<=n;++i){
ans=(ans+k*(h[i-1]*t[i+1]%p))%p;
k=(k*q)%p;
}
这样。
卡卡常,多用int,少%,这道题就惨痛地A了。
最新文章
- Orchard源码分析(7):ASP.NET MVC相关
- 通信原理实践(四)&mdash;&mdash;模拟通信系统性能分析
- ubuntu 配置JDK环境
- 有关CLR的初学小整理2(可能理解不深刻,望大牛指出)
- [zz]Java中的instanceof关键字
- Objective-C关于数据处理
- python程序中自启动appium服务
- IPC$命令详解
- C#判断输入的是否是汉字
- android学习——android架构
- Windows10 Apache2.4 PHP7 MySQL 5.7安装教程
- 遍历Arraylist的方法
- [Swift]LeetCode156.二叉树的上下颠倒 $ Binary Tree Upside Down
- 大数据开发主战场hive (企业hive应用)
- openssl dhparam(密钥交换)
- class ObjectOutputStream也是过滤流,使节点流直接获得输出对象。
- ubuntu 应用添加进环境变量
- 深入浅出的webpack4构建工具---Scope Hoisting(十六)
- Object.keys()返回对象的属性
- Sofware-Engineering Zero