Submission #945446
Source Code Expand
#include<iostream> #include<cstdio> #include<algorithm> #include<set> #include<map> #include<queue> #include<cassert> #define PB push_back #define MP make_pair #define sz(v) (in((v).size())) #define forn(i,n) for(in i=0;i<(n);++i) #define forv(i,v) forn(i,sz(v)) #define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i) #define all(v) (v).begin(),(v).end() using namespace std; typedef long long in; typedef vector<in> VI; typedef vector<VI> VVI; const in mdl=1000000007LL; VI fc,invfc; in ncr(in a, in b){ if(b==0 || b==a) return 1;//even if a<0 if(b<0 || b>a) return 0; return fc[a]*invfc[b]%mdl*invfc[a-b]%mdl; } void inifc(){ const in mxfc=1001000; fc.resize(mxfc); invfc.resize(mxfc); fc[0]=fc[1]=invfc[0]=invfc[1]=1; for(in i=2;i<mxfc;++i){ fc[i]=fc[i-1]*i%mdl; invfc[i]=invfc[mdl%i]*(mdl-mdl/i)%mdl; } for(in i=2;i<mxfc;++i){ invfc[i]*=invfc[i-1]; invfc[i]%=mdl; } } in n; VI mar; VI fr; in bef(in a){ return lower_bound(all(fr),a)-fr.begin(); } struct fenw{ VI fw; in n; void ini(in pn){ n=pn; fw.clear(); fw.resize(n,0); } void ad(in l, in x){ while(l<n){ fw[l]+=x; l|=(l+1); } } in sm(in l){ in r=0; while(l>=0){ r+=fw[l]; l&=(l+1); --l; } return r; } }; VI rfr; fenw ff; int main(){ ios::sync_with_stdio(0); cin.tie(0); inifc(); in sm=0; cin>>n; ff.ini(n+3); mar.resize(n); forn(i,n) cin>>mar[i]; rfr.resize(n+1,1); rfr[0]=0; forn(i,n) rfr[mar[i]]=0; for(in i=1;i<=n;++i){ if(rfr[i]) fr.PB(i); } in ranksum=0; forv(i,fr) ranksum+=fr[i]-1; ranksum%=mdl; in cval; in crank; in usd0=0; in pfr=sz(fr)-1; if(pfr==-1) pfr=0; else pfr=fc[pfr]; sm+=fc[sz(fr)]; in cbef; in inv2=(mdl+1)/2; forn(i,n){ if(i==n-1) cval=0; else cval=fc[n-1-i]; if(mar[i]!=0){ crank=mar[i]-1-ff.sm(mar[i]); sm+=crank*cval%mdl*fc[sz(fr)]; cbef=bef(mar[i]); sm-=cbef*usd0%mdl*pfr%mdl*cval; sm%=mdl; ff.ad(mar[i],1); ranksum-=sz(fr)-cbef; ranksum%=mdl; } else{ sm+=ranksum*cval%mdl*pfr; sm-=fc[sz(fr)]*usd0%mdl*inv2%mdl*cval; sm%=mdl; ++usd0; } } sm%=mdl; if(sm<0) sm+=mdl; cout<<sm<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Encyclopedia of Permutations |
User | w4yneb0t |
Language | C++14 (GCC 5.4.1) |
Score | 1200 |
Code Size | 2450 Byte |
Status | AC |
Exec Time | 184 ms |
Memory | 31856 KB |
Judge Result
Set Name | Sample | Subtask | All | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 500 / 500 | 700 / 700 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 0_004.txt |
Subtask | 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 0_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt |
All | 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 0_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.txt, 1_023.txt, 1_024.txt, 1_025.txt, 1_026.txt, 1_027.txt, 1_028.txt, 1_029.txt, 1_030.txt, 1_031.txt, 1_032.txt, 2_033.txt, 2_034.txt, 2_035.txt, 2_036.txt, 2_037.txt, 2_038.txt, 2_039.txt, 2_040.txt, 2_041.txt, 2_042.txt, 2_043.txt, 2_044.txt, 2_045.txt, 2_046.txt, 2_047.txt, 2_048.txt, 2_049.txt, 2_050.txt, 2_051.txt, 2_052.txt, 2_053.txt, 2_054.txt, 2_055.txt, 2_056.txt, 2_057.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
0_000.txt | AC | 51 ms | 15872 KB |
0_001.txt | AC | 52 ms | 15872 KB |
0_002.txt | AC | 51 ms | 15872 KB |
0_003.txt | AC | 51 ms | 15872 KB |
0_004.txt | AC | 51 ms | 15872 KB |
1_005.txt | AC | 52 ms | 15872 KB |
1_006.txt | AC | 52 ms | 15872 KB |
1_007.txt | AC | 51 ms | 15872 KB |
1_008.txt | AC | 52 ms | 16000 KB |
1_009.txt | AC | 52 ms | 16000 KB |
1_010.txt | AC | 52 ms | 16000 KB |
1_011.txt | AC | 52 ms | 16000 KB |
1_012.txt | AC | 53 ms | 16000 KB |
1_013.txt | AC | 51 ms | 16000 KB |
1_014.txt | AC | 52 ms | 16000 KB |
1_015.txt | AC | 52 ms | 16000 KB |
1_016.txt | AC | 52 ms | 16000 KB |
1_017.txt | AC | 52 ms | 15872 KB |
1_018.txt | AC | 52 ms | 16000 KB |
1_019.txt | AC | 52 ms | 16000 KB |
1_020.txt | AC | 52 ms | 16000 KB |
1_021.txt | AC | 52 ms | 16000 KB |
1_022.txt | AC | 52 ms | 16000 KB |
1_023.txt | AC | 52 ms | 16000 KB |
1_024.txt | AC | 52 ms | 16000 KB |
1_025.txt | AC | 51 ms | 15872 KB |
1_026.txt | AC | 52 ms | 16000 KB |
1_027.txt | AC | 51 ms | 16000 KB |
1_028.txt | AC | 52 ms | 16000 KB |
1_029.txt | AC | 52 ms | 16000 KB |
1_030.txt | AC | 52 ms | 16000 KB |
1_031.txt | AC | 52 ms | 16000 KB |
1_032.txt | AC | 52 ms | 16000 KB |
2_033.txt | AC | 109 ms | 31856 KB |
2_034.txt | AC | 80 ms | 23924 KB |
2_035.txt | AC | 124 ms | 31856 KB |
2_036.txt | AC | 118 ms | 30960 KB |
2_037.txt | AC | 139 ms | 31856 KB |
2_038.txt | AC | 128 ms | 30448 KB |
2_039.txt | AC | 153 ms | 31856 KB |
2_040.txt | AC | 98 ms | 23924 KB |
2_041.txt | AC | 165 ms | 31856 KB |
2_042.txt | AC | 70 ms | 18812 KB |
2_043.txt | AC | 173 ms | 29812 KB |
2_044.txt | AC | 129 ms | 25716 KB |
2_045.txt | AC | 182 ms | 29812 KB |
2_046.txt | AC | 173 ms | 29300 KB |
2_047.txt | AC | 184 ms | 28792 KB |
2_048.txt | AC | 105 ms | 21756 KB |
2_049.txt | AC | 183 ms | 28284 KB |
2_050.txt | AC | 136 ms | 24188 KB |
2_051.txt | AC | 144 ms | 27648 KB |
2_052.txt | AC | 133 ms | 26496 KB |
2_053.txt | AC | 108 ms | 31856 KB |
2_054.txt | AC | 144 ms | 27648 KB |
2_055.txt | AC | 127 ms | 27648 KB |
2_056.txt | AC | 127 ms | 27648 KB |
2_057.txt | AC | 131 ms | 29812 KB |