Submission #946212
Source Code Expand
// {{{ by shik
#include <bits/stdc++.h>
#include <unistd.h>
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x),end(x)
#define REP(i,n) for ( int i=0; i<int(n); i++ )
#define REP1(i,a,b) for ( int i=(a); i<=int(b); i++ )
#define FOR(it,c) for ( auto it=(c).begin(); it!=(c).end(); it++ )
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;
#ifdef SHIK
template<typename T>
void _dump( const char* s, T&& head ) { cerr<<s<<"="<<head<<endl; }
template<typename T, typename... Args>
void _dump( const char* s, T&& head, Args&&... tail ) {
int c=0;
while ( *s!=',' || c!=0 ) {
if ( *s=='(' || *s=='[' || *s=='{' ) c++;
if ( *s==')' || *s==']' || *s=='}' ) c--;
cerr<<*s++;
}
cerr<<"="<<head<<", ";
_dump(s+1,tail...);
}
#define dump(...) do { \
fprintf(stderr, "%s:%d - ", __PRETTY_FUNCTION__, __LINE__); \
_dump(#__VA_ARGS__, __VA_ARGS__); \
} while (0)
template<typename Iter>
ostream& _out( ostream &s, Iter b, Iter e ) {
s<<"[";
for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
s<<"]";
return s;
}
template<typename A, typename B>
ostream& operator <<( ostream &s, const pair<A,B> &p ) { return s<<"("<<p.first<<","<<p.second<<")"; }
template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) { return _out(s,ALL(c)); }
template<typename T, size_t N>
ostream& operator <<( ostream &s, const array<T,N> &c ) { return _out(s,ALL(c)); }
template<typename T>
ostream& operator <<( ostream &s, const set<T> &c ) { return _out(s,ALL(c)); }
template<typename A, typename B>
ostream& operator <<( ostream &s, const map<A,B> &c ) { return _out(s,ALL(c)); }
#else
#define dump(...)
#endif
template<typename T>
void _R( T &x ) { cin>>x; }
void _R( int &x ) { scanf("%d",&x); }
void _R( long long &x ) { scanf("%" PRId64,&x); }
void _R( double &x ) { scanf("%lf",&x); }
void _R( char &x ) { scanf(" %c",&x); }
void _R( char *x ) { scanf("%s",x); }
void R() {}
template<typename T, typename... U>
void R( T& head, U&... tail ) {
_R(head);
R(tail...);
}
template<typename T>
void _W( const T &x ) { cout<<x; }
void _W( const int &x ) { printf("%d",x); }
template<typename T>
void _W( const vector<T> &x ) {
for ( auto i=x.cbegin(); i!=x.cend(); i++ ) {
if ( i!=x.cbegin() ) putchar(' ');
_W(*i);
}
}
void W() {}
template<typename T, typename... U>
void W( const T& head, const U&... tail ) {
_W(head);
putchar(sizeof...(tail)?' ':'\n');
W(tail...);
}
#ifdef SHIK
#define FILEIO(...)
#else
#define FILEIO(name) do {\
freopen(name ".in","r",stdin); \
freopen(name ".out","w",stdout); \
} while (0)
#endif
// }}}
template<typename T>
struct BIT {
int n;
vector<T> a;
void init(int _n) {
n = _n;
a.resize(n + 1);
a.clear();
}
void ins(int x, T v) {
for (int i = x; i <= n; i += i & -i) {
a[i] += v;
}
}
T ask(int x) {
T s = 0;
for (int i = x; i; i -= i & -i) {
s += a[i];
}
return s;
}
T ask(int l, int r) {
auto s = ask(r);
if (l > 0) {
s += ask(l - 1);
}
return s;
}
};
BIT<int> bit;
const int N=5e5+10;
const LL MOD=1e9+7;
int inv[N],fac[N],ifac[N];
void predo() {
inv[1]=1;
REP1(i,2,N-1) inv[i]=1LL*inv[MOD%i]*(MOD-MOD/i)%MOD;
fac[0]=fac[1]=ifac[0]=ifac[1]=1;
REP1(i,2,N-1) fac[i]=1LL*fac[i-1]*i%MOD;
REP1(i,2,N-1) ifac[i]=1LL*ifac[i-1]*inv[i]%MOD;
}
LL C( int n, int m ) {
if ( m>n ) return 0;
return 1LL*fac[n]*ifac[m]%MOD*ifac[n-m]%MOD;
}
int n,a[N],c[N],gt[N];
LL sgt[N];
int main() {
predo();
R(n);
REP1(i,1,n) R(a[i]);
REP1(i,1,n) if ( a[i] ) c[a[i]]++;
REP1(i,1,n) c[i]+=c[i-1];
LL sz=0;
REP1(i,1,n) if ( a[i]==0 ) sz++;
REP1(i,1,n) if ( a[i] ) {
int lt=a[i]-c[a[i]];
gt[i]=sz-lt;
}
for ( int i=n; i>=1; i-- ) sgt[i]=(sgt[i+1]+gt[i])%MOD;
bit.init(n);
REP1(i,1,n) if ( a[i] ) bit.ins(a[i],1);
LL ans=0;
LL z=sz;
REP1(i,1,n) {
LL e;
if ( a[i]==0 ) {
z--;
e=z*inv[2]%MOD;
e=(e+sgt[i]*inv[sz])%MOD;
} else {
bit.ins(a[i],-1);
LL base=bit.ask(a[i]);
if ( z==0 ) {
e=base;
} else {
LL lt=a[i]-c[a[i]];
e=(base+lt*inv[sz]%MOD*z)%MOD;
}
}
LL now=e*fac[sz]%MOD;
now=now*fac[n-i]%MOD;
ans+=now;
dump(i,a[i],e*fac[sz]%MOD,now);
}
ans+=fac[sz];
ans%=MOD;
W(ans);
return 0;
}
Submission Info
Submission Time
2016-10-23 22:12:07+0900
Task
E - Encyclopedia of Permutations
User
shik
Language
C++14 (GCC 5.4.1)
Score
1200
Code Size
4899 Byte
Status
AC
Exec Time
137 ms
Memory
17920 KB
Compile Error
./Main.cpp: In function ‘void _R(long long int&)’:
./Main.cpp:62:46: warning: format ‘%ld’ expects argument of type ‘long int*’, but argument 2 has type ‘long long int*’ [-Wformat=]
void _R( long long &x ) { scanf("%" PRId64,&x); }
^
./Main.cpp: In function ‘void _R(int&)’:
./Main.cpp:61:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
void _R( int &x ) { scanf("%d",&x); }
^
./Main.cpp: In function ‘void _R(long long int&)’:
./Main.cpp:62:47: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
void _R( long long &x ) { scanf("%" PRId64,&x); }
^
./Main.cpp: In function ‘void _R(double&)’:
./Main.cpp:63:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-resu...
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
24 ms
6144 KB
0_001.txt
AC
24 ms
6144 KB
0_002.txt
AC
24 ms
6144 KB
0_003.txt
AC
24 ms
6144 KB
0_004.txt
AC
24 ms
6144 KB
1_005.txt
AC
24 ms
6144 KB
1_006.txt
AC
24 ms
6144 KB
1_007.txt
AC
24 ms
6144 KB
1_008.txt
AC
24 ms
6144 KB
1_009.txt
AC
24 ms
6144 KB
1_010.txt
AC
24 ms
6144 KB
1_011.txt
AC
24 ms
6144 KB
1_012.txt
AC
25 ms
6144 KB
1_013.txt
AC
24 ms
6144 KB
1_014.txt
AC
25 ms
6144 KB
1_015.txt
AC
24 ms
6144 KB
1_016.txt
AC
24 ms
6144 KB
1_017.txt
AC
24 ms
6144 KB
1_018.txt
AC
25 ms
6144 KB
1_019.txt
AC
24 ms
6144 KB
1_020.txt
AC
25 ms
6144 KB
1_021.txt
AC
24 ms
6144 KB
1_022.txt
AC
25 ms
6144 KB
1_023.txt
AC
24 ms
6144 KB
1_024.txt
AC
25 ms
6144 KB
1_025.txt
AC
24 ms
6144 KB
1_026.txt
AC
25 ms
6144 KB
1_027.txt
AC
24 ms
6144 KB
1_028.txt
AC
24 ms
6144 KB
1_029.txt
AC
25 ms
6144 KB
1_030.txt
AC
25 ms
6144 KB
1_031.txt
AC
25 ms
6144 KB
1_032.txt
AC
24 ms
6144 KB
2_033.txt
AC
79 ms
15872 KB
2_034.txt
AC
52 ms
11008 KB
2_035.txt
AC
89 ms
17792 KB
2_036.txt
AC
83 ms
16896 KB
2_037.txt
AC
97 ms
17792 KB
2_038.txt
AC
88 ms
16384 KB
2_039.txt
AC
106 ms
17920 KB
2_040.txt
AC
64 ms
11904 KB
2_041.txt
AC
112 ms
17792 KB
2_042.txt
AC
40 ms
8320 KB
2_043.txt
AC
117 ms
17792 KB
2_044.txt
AC
85 ms
13824 KB
2_045.txt
AC
122 ms
17792 KB
2_046.txt
AC
118 ms
17280 KB
2_047.txt
AC
127 ms
17792 KB
2_048.txt
AC
67 ms
11264 KB
2_049.txt
AC
131 ms
17792 KB
2_050.txt
AC
93 ms
13824 KB
2_051.txt
AC
130 ms
17792 KB
2_052.txt
AC
119 ms
16640 KB
2_053.txt
AC
80 ms
15872 KB
2_054.txt
AC
137 ms
17792 KB
2_055.txt
AC
110 ms
17792 KB
2_056.txt
AC
110 ms
17792 KB
2_057.txt
AC
98 ms
17792 KB