Submission #946030

---

Source Code Expand

#include<stdio.h>
#include<algorithm>
using namespace std;
long long mod=1000000007;
int M=510000;
long long inv[510000];
long long fact[510000];
long long factinv[510000];
int b[510000];
int at[510000];
int v[510000];
pair<int,int> p[510000];
int bit[510000];
int sum(int a,int b){
	if(a)return sum(0,b)-sum(0,a-1);
	int ret=0;
	for(;b>=0;b=(b&(b+1))-1)ret+=bit[b];
	return ret;
}
void add(int a,int b){
	for(;a<510000;a|=a+1)bit[a]+=b;
}
int main(){
	inv[1]=fact[0]=factinv[0]=1;
	for(int i=2;i<M;i++)inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
	for(int i=1;i<M;i++)fact[i]=fact[i-1]*i%mod;
	for(int i=1;i<M;i++)factinv[i]=factinv[i-1]*inv[i]%mod;
	int a;scanf("%d",&a);
	int ind=0;
	for(int i=0;i<a;i++){
		scanf("%d",b+i);
		b[i]--;
		v[b[i]]++;
		if(b[i]>=0){
			p[ind++]=make_pair(b[i],i);
		}
	}
	int sz=0;
	for(int i=0;i<a;i++)if(!v[i])at[sz++]=i;
	long long ret=0;
	int cnt=0;
	long long ad=0;
	long long hu=0;
	long long ks=1;
	int ps=0;
	for(int i=0;i<a;i++)if(b[i]==-1)ps++;
	for(int i=a-1;i>=0;i--){
		
		if(b[i]==-1){
			cnt++;
			ret=(ret+(long long)(cnt)*(cnt-1)/2%mod*inv[cnt]%mod*fact[ps]%mod*ks)%mod;
			ret=(ret+ad%mod*inv[sz]%mod*ks%mod*fact[ps])%mod;
		}else{
			int ts=sum(0,b[i]);
			hu=(hu+(long long)ts*ks%mod)%mod;
			int tmp=lower_bound(at,at+sz,b[i])-at;
			hu=(hu+(long long)tmp*cnt%mod*inv[sz]%mod*ks)%mod;
			add(b[i],1);
			ad+=sz-tmp;
		}
	//	printf("%lld\n",ret);
		ks=ks*(a-i)%mod;
	}
	//printf("%lld\n",ret);
	ret=(ret+fact[cnt])%mod;
	ret=(ret+hu%mod*fact[cnt])%mod;
	printf("%lld\n",ret);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:28:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  int a;scanf("%d",&a);
                      ^
./Main.cpp:31:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",b+i);
                  ^

Judge Result