Submission #947950
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define REACH cerr<<"reached line "<<__LINE__<<endl
#define DBG(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl
using uint=unsigned int;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using ld=long double;
template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
os<<"("<<p.first<<","<<p.second<<")";
return os;
}
template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
os<<"[";
REP(i,(int)v.size()){
if(i)os<<",";
os<<v[i];
}
os<<"]";
return os;
}
int read(){
int i;
scanf("%d",&i);
return i;
}
ll readLL(){
ll i;
scanf("%lld",&i);
return i;
}
string readString(){
static char buf[3341919];
scanf("%s",buf);
return string(buf);
}
char* readCharArray(){
static char buf[3341919];
static int bufUsed=0;
char* ret=buf+bufUsed;
scanf("%s",ret);
bufUsed+=strlen(ret)+1;
return ret;
}
template<class T,class U>
void chmax(T& a,U b){
if(a<b)
a=b;
}
template<class T,class U>
void chmin(T& a,U b){
if(a>b)
a=b;
}
template<class T>
T Sq(const T& t){
return t*t;
}
const int mod=1000000007;
template<class T,class U>
void add(T& a,U b){
a=((ll)a+b)%mod;
}
template<>
void add(int& a,int b){
a+=b;
if(a>=mod)a-=mod;
}
template<class T,class U>
void sub(T& a,U b){
a=((ll)a-b%mod+mod)%mod;
}
template<>
void sub(int& a,int b){
a-=b;
if(a<0)a+=mod;
}
template<class T,class U>
void mult(T& a,U b){
a=((ll)a*b)%mod;
}
ll modPow(ll a,ll p){
ll s=1;
REP(i,30){
if((p>>i)&1)
mult(s,a);
mult(a,a);
}
return s;
}
ll modInv(ll a){
return modPow(a,mod-2);
}
struct BIT{
vi d;
void Init(int n){
d.assign(n,0);
}
void Add(int i,int v){
while(i<(int)d.size()){
d[i]+=v;
i+=(i+1)&(-i-1);
}
}
int Get(int i){
int ret=0;
while(i>=0){
ret+=d[i];
i-=(i+1)&(-i-1);
}
return ret;
}
};
int main(){
vector<ll> fact({1});
FOR(i,1,1141919)
fact.PB(fact.back()*i%mod);
auto comb=[&](int a,int b){
if(a<0||b<0||b>a)
return 0LL;
return fact[a]*modInv(fact[b])%mod*modInv(fact[a-b])%mod;
};
int n=read();
vi p;
vector<bool> canUse(n,true);
REP(i,n){
int x=read()-1;
p.PB(x);
if(x>=0)
canUse[x]=false;
}
vi w;
REP(i,n)if(canUse[i])
w.PB(i);
ll ans=0;
BIT bit;
bit.Init(n);
ll q=0;
int sel=0;
for(int i=n-1;i>=0;i--){
if(p[i]!=-1){
int low=bit.Get(p[i]);
int canSel=lower_bound(w.begin(),w.end(),p[i])-w.begin();
add(ans,fact[n-1-i]*low%mod*
comb((int)w.size(),sel)%mod*fact[sel]%mod*fact[(int)w.size()-sel]);
add(ans,fact[n-1-i]*canSel%mod
*comb((int)w.size()-1,sel-1)%mod*fact[sel]%mod*fact[(int)w.size()-sel]);
bit.Add(p[i],1);
q+=(int)w.size()-canSel;
q%=mod;
}else{
add(ans,fact[n-1-i]*q%mod
*comb((int)w.size()-1,sel)%mod*fact[sel]%mod*fact[(int)w.size()-1-sel]);
add(ans,fact[n-1-i]*(((ll)w.size()*((int)w.size()-1)/2)%mod)%mod
*comb((int)w.size()-1-1,sel-1)%mod*fact[sel]%mod*fact[(int)w.size()-1-sel]);
sel++;
}
}
cout<<(ans+fact[sel])%mod<<endl;
}
Submission Info
Compile Error
./Main.cpp: In function ‘int read()’:
./Main.cpp:36:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&i);
^
./Main.cpp: In function ‘ll readLL()’:
./Main.cpp:42:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&i);
^
./Main.cpp: In function ‘std::string readString()’:
./Main.cpp:48:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",buf);
^
./Main.cpp: In function ‘char* readCharArray()’:
./Main.cpp:56:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s",ret);
^
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 |
40 ms |
16744 KB |
0_001.txt |
AC |
40 ms |
16744 KB |
0_002.txt |
AC |
40 ms |
16744 KB |
0_003.txt |
AC |
40 ms |
16744 KB |
0_004.txt |
AC |
40 ms |
16744 KB |
1_005.txt |
AC |
40 ms |
16744 KB |
1_006.txt |
AC |
40 ms |
16744 KB |
1_007.txt |
AC |
40 ms |
16744 KB |
1_008.txt |
AC |
42 ms |
16744 KB |
1_009.txt |
AC |
41 ms |
16744 KB |
1_010.txt |
AC |
42 ms |
16744 KB |
1_011.txt |
AC |
41 ms |
16744 KB |
1_012.txt |
AC |
42 ms |
16744 KB |
1_013.txt |
AC |
41 ms |
16744 KB |
1_014.txt |
AC |
42 ms |
16744 KB |
1_015.txt |
AC |
41 ms |
16744 KB |
1_016.txt |
AC |
42 ms |
16744 KB |
1_017.txt |
AC |
40 ms |
16744 KB |
1_018.txt |
AC |
42 ms |
16744 KB |
1_019.txt |
AC |
41 ms |
16744 KB |
1_020.txt |
AC |
42 ms |
16744 KB |
1_021.txt |
AC |
41 ms |
16744 KB |
1_022.txt |
AC |
42 ms |
16744 KB |
1_023.txt |
AC |
41 ms |
16744 KB |
1_024.txt |
AC |
42 ms |
16744 KB |
1_025.txt |
AC |
40 ms |
16744 KB |
1_026.txt |
AC |
41 ms |
16744 KB |
1_027.txt |
AC |
40 ms |
16744 KB |
1_028.txt |
AC |
41 ms |
16744 KB |
1_029.txt |
AC |
42 ms |
16744 KB |
1_030.txt |
AC |
41 ms |
16744 KB |
1_031.txt |
AC |
41 ms |
16744 KB |
1_032.txt |
AC |
42 ms |
16744 KB |
2_033.txt |
AC |
399 ms |
16744 KB |
2_034.txt |
AC |
219 ms |
16744 KB |
2_035.txt |
AC |
414 ms |
16744 KB |
2_036.txt |
AC |
382 ms |
16744 KB |
2_037.txt |
AC |
426 ms |
16744 KB |
2_038.txt |
AC |
378 ms |
16744 KB |
2_039.txt |
AC |
440 ms |
16744 KB |
2_040.txt |
AC |
236 ms |
16744 KB |
2_041.txt |
AC |
449 ms |
16744 KB |
2_042.txt |
AC |
116 ms |
16744 KB |
2_043.txt |
AC |
459 ms |
16744 KB |
2_044.txt |
AC |
313 ms |
16744 KB |
2_045.txt |
AC |
470 ms |
16744 KB |
2_046.txt |
AC |
448 ms |
16744 KB |
2_047.txt |
AC |
473 ms |
16744 KB |
2_048.txt |
AC |
228 ms |
16744 KB |
2_049.txt |
AC |
475 ms |
16744 KB |
2_050.txt |
AC |
323 ms |
16744 KB |
2_051.txt |
AC |
282 ms |
16744 KB |
2_052.txt |
AC |
257 ms |
16744 KB |
2_053.txt |
AC |
399 ms |
16744 KB |
2_054.txt |
AC |
428 ms |
16744 KB |
2_055.txt |
AC |
270 ms |
16744 KB |
2_056.txt |
AC |
273 ms |
16744 KB |
2_057.txt |
AC |
424 ms |
16744 KB |