結果

問題 No.696 square1001 and Permutation 5
ユーザー rapurasu
提出日時 2018-07-13 10:39:47
言語 C++11
(gcc 4.8.5)
結果
WA   .
実行時間 -
コード長 1,368 Byte
コンパイル時間 874 ms
使用メモリ 3,056 KB
最終ジャッジ日時 2018-09-26 00:40:21

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
99_challenge1.txt WA -
in_01.txt WA -
in_02.txt WA -
in_03.txt WA -
in_04.txt WA -
in_05.txt WA -
in_06.txt WA -
in_07.txt WA -
in_08.txt WA -
in_09.txt WA -
in_10.txt WA -
in_11.txt AC 40 ms
3,052 KB
sample_1.txt AC 4 ms
2,280 KB
sample_2.txt AC 4 ms
2,280 KB
テストケース一括ダウンロード

ソースコード

diff #
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
int N;
LL A[100001];
int p[100001];

#define BITTYPE int

#define BITCNT  2

#define BITSIZE 512345

namespace _BIT{

    int i=0;

    BITTYPE t[2][BITSIZE];

    inline BITTYPE* get(){

        return t[i++];

    }

}



struct BIT{

    using T=BITTYPE;

    T *t;

    int n;

    BIT(int N):t(_BIT::get()),n(N+1){

        REP(i,n+1)t[i]=0;

    }

    void add(int r,T v){//add v for [1,r]

        for(;r;r-=r&-r)t[r]+=v;

    }

    void add(int l,int r,T v){//add v for [l,r]

        add(r,v);

        add(l-1,-v);

    }

    T get(int i){//get sum[i]

        T res=0;

        for(;i<=n;i+=i&-i)res+=t[i];

        return res;

    }

};

LL MOD=1e9+7;
void kai(){
	A[0]=1;
	REP(i,100001){
		if(i==0)continue;
		A[i]=A[i-1]*i;
		A[i]%=MOD;
	}
	A[0]=0;
}

int main(){
	kai();
	cin>>N;
	REP(i,N){
		cin>>p[i];
	}
	BIT b(N+10);
	REP(i,N+10){
		b.add(i+1,N+9,1);
	}
	/*REP(i,10){
		cout<<"aa";
		cout<<b.get(i+1)<<endl;
	}*/
	LL ans=0;
	REP(i,N){
		int a=b.get(p[i]);
		b.add(p[i],N+9,-1);
		a--;
		int bb=N-(i+1);
		ans+=(a*A[bb]);
		ans%=MOD;
		//cout<<a<<" "<<ans<<endl;
	}
	cout<<ans+1<<endl;
	return(0);
}
0