Submission #945523


Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <map>
#include <set>
#include <functional>
#include <cmath>
#define SIZE 500005
#define MOD 1000000007

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

struct BIT
{
	int bit[SIZE];
	
	void init()
	{
		memset(bit,0,sizeof(bit));
	}
	void add(int k,int x)
	{
		while(k<SIZE)
		{
			bit[k]+=x;
			k+=k&-k;
		}
	}
	int get(int k)
	{
		int ret=0;
		while(k>0)
		{
			ret+=bit[k];
			k-=k&-k;
		}
		return ret;
	}
	int get(int s,int t)
	{
		return get(t)-get(s-1);
	}
};
BIT bit;
ll inv[SIZE],fac[SIZE],finv[SIZE];
void make()
{
	fac[0]=fac[1]=1;
	finv[0]=finv[1]=1;
	inv[1]=1;
	for(int i=2;i<SIZE;i++)
	{
		inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
		fac[i]=fac[i-1]*(ll) i%MOD;
		finv[i]=finv[i-1]*inv[i]%MOD;
	}
}
ll C(int a,int b)
{
	if(a<b) return 0;
	return fac[a]*(finv[b]*finv[a-b]%MOD)%MOD;
}
int A[SIZE];
ll sum[SIZE];
bool use[SIZE];

int main()
{
	make();
	int n;
	scanf("%d",&n);
	int cnt=0;
	for(int i=0;i<n;i++)
	{
		scanf("%d",&A[i]);
		if(A[i]>=1) use[A[i]]=true;
	}
	vector <int> zan;
	for(int i=1;i<=n;i++) if(!use[i]) zan.push_back(i);
	int now=0;
	ll st=0;
	ll ret=fac[zan.size()];
	bit.init();
	for(int i=n-1;i>=0;i--)
	{
		if(A[i]==0)
		{
			now++;
			ll way=C(zan.size(),now)*C(now,2)%MOD*fac[now-1]%MOD*fac[zan.size()-now]%MOD;
			way+=st*fac[zan.size()-1]%MOD;
			if(way>=MOD) way-=MOD;
			sum[i]=way;
		}
		else
		{
			int pos=lower_bound(zan.begin(),zan.end(),A[i])-zan.begin();
			st+=zan.size()-pos;
			if(now>=1)
			{
				sum[i]=(ll) pos*C(zan.size()-1,now-1)%MOD*fac[zan.size()-now]%MOD*fac[now]%MOD;
			}
			sum[i]+=(ll) bit.get(A[i])*(ll) fac[zan.size()]%MOD;
			if(sum[i]>=MOD) sum[i]-=MOD;
			bit.add(A[i],1);
			st%=MOD;
		}
		ret+=sum[i]*fac[n-i-1]%MOD;
		if(ret>=MOD) ret-=MOD;
		//printf("%lld\n",sum[i]);
	}
	printf("%lld\n",ret);
	return 0;
}

Submission Info

Submission Time
Task E - Encyclopedia of Permutations
User yutaka1999
Language C++14 (GCC 5.4.1)
Score 1200
Code Size 2037 Byte
Status AC
Exec Time 159 ms
Memory 22128 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:76:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
./Main.cpp:80:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&A[i]);
                    ^

Judge Result

Set Name Sample Subtask All
Score / Max Score 0 / 0 500 / 500 700 / 700
Status
AC × 5
AC × 33
AC × 58
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 23 ms 13952 KB
0_001.txt AC 24 ms 13952 KB
0_002.txt AC 24 ms 13952 KB
0_003.txt AC 24 ms 13952 KB
0_004.txt AC 23 ms 13952 KB
1_005.txt AC 24 ms 13952 KB
1_006.txt AC 23 ms 13952 KB
1_007.txt AC 24 ms 13952 KB
1_008.txt AC 24 ms 13952 KB
1_009.txt AC 24 ms 13952 KB
1_010.txt AC 24 ms 13952 KB
1_011.txt AC 24 ms 13952 KB
1_012.txt AC 24 ms 13952 KB
1_013.txt AC 24 ms 13952 KB
1_014.txt AC 24 ms 13952 KB
1_015.txt AC 24 ms 13952 KB
1_016.txt AC 24 ms 13952 KB
1_017.txt AC 24 ms 13952 KB
1_018.txt AC 24 ms 13952 KB
1_019.txt AC 24 ms 13952 KB
1_020.txt AC 24 ms 13952 KB
1_021.txt AC 24 ms 13952 KB
1_022.txt AC 24 ms 13952 KB
1_023.txt AC 24 ms 13952 KB
1_024.txt AC 24 ms 13952 KB
1_025.txt AC 24 ms 13952 KB
1_026.txt AC 24 ms 13952 KB
1_027.txt AC 24 ms 13952 KB
1_028.txt AC 24 ms 14080 KB
1_029.txt AC 24 ms 13952 KB
1_030.txt AC 24 ms 13952 KB
1_031.txt AC 24 ms 13952 KB
1_032.txt AC 24 ms 13952 KB
2_033.txt AC 84 ms 21872 KB
2_034.txt AC 54 ms 17908 KB
2_035.txt AC 106 ms 22128 KB
2_036.txt AC 101 ms 21488 KB
2_037.txt AC 118 ms 21872 KB
2_038.txt AC 106 ms 20976 KB
2_039.txt AC 136 ms 21616 KB
2_040.txt AC 75 ms 17908 KB
2_041.txt AC 142 ms 21488 KB
2_042.txt AC 44 ms 15484 KB
2_043.txt AC 151 ms 21236 KB
2_044.txt AC 104 ms 18804 KB
2_045.txt AC 155 ms 20980 KB
2_046.txt AC 150 ms 20724 KB
2_047.txt AC 159 ms 20856 KB
2_048.txt AC 80 ms 17020 KB
2_049.txt AC 158 ms 20604 KB
2_050.txt AC 109 ms 18300 KB
2_051.txt AC 112 ms 20224 KB
2_052.txt AC 102 ms 19712 KB
2_053.txt AC 85 ms 21872 KB
2_054.txt AC 114 ms 20224 KB
2_055.txt AC 99 ms 20224 KB
2_056.txt AC 98 ms 20224 KB
2_057.txt AC 107 ms 21364 KB