5 条题解
-
0
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll, ll> pii; typedef double db; #define fi first #define se second const int P=1e9+7; inline ll fpow(ll a, ll x, ll mod) { ll ans=1; for(;x;x>>=1,a=a*a%mod) if(x&1) ans=ans*a%mod; return ans; } int p[2]={2, P>>1}, phi=p[1]-1; struct exnum{ int x, cnt[2]; exnum() { x=0; cnt[0]=cnt[1]=0; } exnum(int val_) { cnt[0]=cnt[1]=0; for(int i=0; i<2; ++i) while(val_%p[i]==0) ++cnt[i], val_/=p[i]; x=val_; } exnum(int x_, int c0_, int c1_):x(x_) { cnt[0]=c0_; cnt[1]=c1_; } inline int val() const { return fpow(p[0], cnt[0], P-1)*fpow(p[1], cnt[1], P-1)%(P-1)*x%(P-1); } }; inline exnum operator * (const exnum &a, const exnum &b) { return exnum((ll)a.x*b.x%(P-1), a.cnt[0]+b.cnt[0], a.cnt[1]+b.cnt[1]); } inline exnum operator / (const exnum &a, const exnum &b) { return exnum((ll)a.x*fpow(b.x, phi-1, P-1)%(P-1), a.cnt[0]-b.cnt[0], a.cnt[1]-b.cnt[1]); } inline exnum operator * (const exnum &a, int b) { return a*exnum(b); } inline exnum operator / (const exnum &a, int b) { return a/exnum(b); } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, res=1; cin>>n; exnum comb(1); for(int i=1, a; i<=n; ++i) { cin>>a; res=(ll)res*fpow(a, comb.val(), P)%P; if(i<n) comb=comb*(n-i)/i; } cout<<res; cout.flush(); return 0; }
信息
- ID
- 87
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 81
- 已通过
- 30
- 上传者