Submission #651046

#TimeUsernameProblemLanguageResultExecution timeMemory
651046dsyzCryptography (NOI20_crypto)C++17
100 / 100
136 ms15160 KiB
#include <bits/stdc++.h> using namespace std; using ll=long long; #define MAXN (300006) int n; ll P[MAXN], f[MAXN], A[MAXN]; vector<ll> d; struct fen { ll fw[MAXN]; fen() { memset(fw, 0, sizeof fw); } void update(int x,ll nval) { for(;x<MAXN;x+=x&(-x)) fw[x]+=nval; } ll sum(int x) { ll res = 0; for(;x;x-=x&(-x)) res+=fw[x]; return res; } } ft; ll mod=1e9+7; int main(){ f[0]=1; for(int i=1;i<MAXN;++i) f[i]=f[i-1]*i%mod; ios::sync_with_stdio(false); cin.tie(0); cin>>n; for(int i=0;i<n;++i) cin>>P[i], d.push_back(P[i]); sort(d.begin(), d.end()), d.resize(unique(d.begin(), d.end())-d.begin()); for(int i=0;i<n;++i) P[i] = lower_bound(d.begin(), d.end(), P[i]) - d.begin() + 1; for(int i=n-1;i>=0;--i) { A[i] = ft.sum(P[i] - 1); ft.update(P[i], 1); } ll ans = 0; for(int i=0;i<n;++i) { ans += A[i] * f[n-i-1] % mod; ans %= mod; } cout<<(ans+1)%mod<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...