1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int N = 5e6 + 10; 5 ll fac[N], sv[N], inv[N], a[N]; 6 ll n, p, k; 7 void read(ll &x) { 8 x = 0; int f = 1; char ch = getchar(); 9 while (ch < '0' || ch >'9') {if (ch == '-') f = -1; ch = getchar();} 10 while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); 11 x *= f; 12 } 13 ll quickpow(ll x, ll y) { 14 ll ans = 1; 15 while (y) { 16 if (y & 1) ans = ans * x % p; 17 x = x * x % p; 18 y >>= 1; 19 } 20 return ans % p; 21 } 22 signed main() { 23 read(n), read(p), read(k); 24 fac[0] = 1; 25 for (int i = 1; i <= n; i ++) { 26 read(a[i]); 27 fac[i] = fac[i - 1] * a[i] % p; 28 } 29 sv[n] = quickpow(fac[n], p - 2); 30 for (int i = n; i >= 1; i --) sv[i - 1] = sv[i] * a[i] % p; 31 ll tmp = 1, ans = 0; 32 for (int i = 1; i <= n; i ++) { 33 tmp = (tmp * k) % p; 34 ans = (ans + ((sv[i] * fac[i - 1] % p)) * tmp) % p; 35 } 36 printf("%lld\n", ans); 37 return 0; 38 }
标签:ch,int,ll,sv,read,P5431,逆元,ans,模板 From: https://www.cnblogs.com/yhxnoerror/p/16753991.html