$O(n+log(mod))$求乘法逆元的方法

时间：2022-07-27 15:34:25

题目

LOJ #152. 乘法逆元 2

题解

一个奇技淫巧qwq。可以离线求乘法逆元，效率\(O(n+log(mod))\)。

考虑处理出\(s_n\)表示\(\prod_{i=1}^na_i\)。以及\(sinv_n\)表示\(\prod_{i=1}^na_i\)的逆元。

那么对于每次询问，\(sinv_i*s_{i-1}\)就是答案。

\(s_i\)显然可以在输入的时候顺便处理出来，\(sinv_n=(s_n)^{mod-2}\)（如果\(mod\)不是质数就exgcd一下）。

对于\(sinv_i(i\not = n)\)，显然有\(sinv_i=sinv_{i+1}*a_{i+1}\)。则可以\(O(n+log(mod))\)求出来\(sinv_i\)。

总复杂度是\(O(n+log(mod))\)的

#include <bits/stdc++.h>

#define ll long long

#define inf 0x3f3f3f3f

#define il inline

namespace io {

#define in(a) a = read()

#define out(a) write(a)

#define outn(a) out(a), putchar('\n')

#define I_int ll

inline I_int read() {

    I_int x = 0, f = 1;

    char c = getchar();

    while (c < '0' || c > '9') {

        if (c == '-') f = -1;

        c = getchar();

    }

    while (c >= '0' && c <= '9') {

        x = x * 10 + c - '0';

        c = getchar();

    }

    return x * f;

}

char F[200];

inline void write(I_int x) {

    if (x == 0) return (void) (putchar('0'));

    I_int tmp = x > 0 ? x : -x;

    if (x < 0) putchar('-');

    int cnt = 0;

    while (tmp > 0) {

        F[cnt++] = tmp % 10 + '0';

        tmp /= 10;

    }

    while (cnt > 0) putchar(F[--cnt]);

}

#undef I_int

}

using namespace io;

using namespace std;

#define N 5000010

const ll mod = 1e9 + 7;

int n = read();

ll sinv[N], a[N], s[N];

ll power(ll a, ll b) { ll ans = 1;

	while(b) {

		if(b & 1) ans = ans * a % mod;

		a = a * a % mod; b >>= 1;

	} return ans;

}

int main() { s[0] = 1;

	for(int i = 1; i <= n; ++i) {

		a[i] = read();

		s[i] = s[i - 1] * a[i] % mod;

	} ll ans = 0;

	sinv[n] = power(s[n], mod - 2); sinv[0] = 1;

	for(int i = n; i; --i) sinv[i - 1] = sinv[i] * a[i] % mod;

	for(int i = 1; i <= n; ++i) {

		ll inv = sinv[i] * s[i - 1] % mod;

		ans = (ans * 998244353 + inv) % mod;

	}

	outn(ans);

}

随机推荐

  1. 第27章 结构型模式大PK

    27.1 代理模式 VS 装饰模式 27.1.1 代理模式 (1)场景:客人找运动员代理要求安排运动员参加比赛 (2)说明:代理人有控制权,可以拒绝客人的要求,也可以答应安排,甚至自己下去跑(因为有些 ...

  2. 余数 2015广工校赛 C 魔幻任务

    题目传送门 题意:问n位最小能整除47的数字 分析:打表发现前面都是100000...,后两位就是100000%47后到47的距离,就是快速幂求1000000%47的值,47-它就是后两位 #incl ...

  3. 一步步学习NHibernate&lpar;6&rpar;——ISession的管理

    请注明转载地址:http://www.cnblogs.com/arhat 今天老魏那个汗啊,我的ThinkPad的电源线不通电了,擦啊.明天还得掏银子买一个!心疼啊,原装的啊.不过话说回来,已经用了将 ...

  4. Tabhost嵌套以及Tab中多个Activity跳转的实现

    做了一个demo,先看看效果图: 源码 如下: () DoubleTabHost package yy.android.tab; import android.app.TabActivity; imp ...

  5. Python调用C&sol;C&plus;&plus;动态链接库

    Python调用C/C++动态链接库 2013年07月26日 ⁄ 综合 ⁄ 共 3219字 ⁄ 字号 小 中 大 ⁄ 评论关闭   吐槽(可略过):不知不觉,4月份毕业,5月份进入团队,已有7个月.大 ...

  6. 【ASP&period;NET Core】JSON Patch 使用简述

    JSON Patch 是啥玩意儿?不知道,直接翻译吧,就叫它“Json 补丁”吧.干吗用的呢?当然是用来修改 JSON 文档的了.那咋修改呢?比较常见有四大操作:AMRR. 咋解释呢? A—— Add ...

  7. 函数计算 Python 连接 SQL Server 小结

    python 连接数据库通常要安装第三方模块,连接 MS SQL Server 需要安装 pymssql .由于 pymsql 依赖于 FreeTDS,对于先于 2.1.3 版本的 pymssql,需 ...

  8. MacOs -bash&colon; warning&colon; setlocale&colon; LC&lowbar;CTYPE&colon; cannot change locale &lpar;UTF-8&rpar;&colon; No such file or directory

    1解决iterm远程登录主机报错 -bash: warning: setlocale: LC_CTYPE: cannot change locale (UTF-8): No such file or ...

  9. Django：模板template（一）

    把模板的过程.语法.标签.反向地址解析.过滤器.模板继承与HTML转义记下笔记 1.概述及demo 动态生成HTML 模板的设计实现业务逻辑(View)和显示内容(template)的分离 一个模板可 ...

  10. POJ 2240 - Arbitrage - &lbrack;bellman-ford求最短路&rsqb;

    Time Limit: 1000MS Memory Limit: 65536K Description Arbitrage is the use of discrepancies in currenc ...

相关文章