整理的算法模板合集： ACM模板

点我看算法全家桶系列！！！

实际上是一个全新的精炼模板整合计划

---

P5431 【模板】乘法逆元2

题目传送门

题目大意：

给定 n n n 个正整数 a i a_i ai​ ，求它们在模 p p p 意义下的乘法逆元。
由于输出太多不好，所以将会给定常数 k k k，你要输出的答案为：

∑ i = 1 n k i a i \sum\limits_{i=1}^n\frac{k^i}{a_i} i=1∑n​ai​ki​

小学数学题

这可卡死我了

O ( n ) O(n) O(n)的复杂度，还要用超级快读才能过…

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include<cctype>

using namespace std;
typedef long long ll;
const int N = 5000007, INF = 2147483646;

//超级快读，不能在本地调试，开了之后本地的其他读入函数也不可使用...
char buf[(int)1e8], *ss = buf;
inline int init() {
    buf[fread(buf, 1, (int)1e8 - 1, stdin)] = '\n';
    fclose(stdin);
    return 0;
}
const int __START__ = init();
inline int read() {
    int d = 0;
    while (!isdigit(*ss)) ++ ss;
    while (isdigit(*ss)) d = d * 10 + (*ss ++ ^'0');
    return d;
}

int n, m, p, k;

ll qpow(ll a, ll b, ll p)
{
    ll res = 1;
    while(b) {
        if(b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res % p;
}

ll inv(ll x) {return qpow(x, p - 2, p);}
/*//模数非质数可以用这个处理模意义下的除法
ll inv(const int x) {
    if(x == 1) return 1;
    return (ll)(p - p / x) * inv(p % x) % p;
}
*/
int a[N];
int pre_sum[N], last_sum[N];
int mul_sum = 1;
ll ans, cnt;

int main()
{
    n = read(), p = read(), k = read();
    for(int i = 1; i <= n; ++ i)
        a[i] = read();

    pre_sum[0] = 1, last_sum[n + 1] = 1;
    for(int i = 1; i <= n; ++ i)
        pre_sum[i] = (ll)pre_sum[i - 1] * a[i] % p;

    for(int i = n; i >= 1; -- i)
        last_sum[i] = (ll)last_sum[i + 1] * a[i] % p;

    ll inv_sum = inv(pre_sum[n]);

    for(int i = 1, j = k; i <= n; ++ i, j = (ll)j * k % p)
        ans = (ans + (ll)j * pre_sum[i - 1] % p * last_sum[i + 1] % p) % p;

    printf("%lld\n", ans * (ll)inv_sum % p);
    return 0;
}