結果

問題 No.696 square1001 and Permutation 5
ユーザー rapurasurapurasu
提出日時 2018-07-13 10:39:47
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 1,368 bytes
コンパイル時間 1,179 ms
コンパイル使用メモリ 158,352 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-07 06:36:34
合計ジャッジ時間 2,365 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 AC 33 ms
5,248 KB
testcase_12 AC 4 ms
5,248 KB
testcase_13 AC 4 ms
5,248 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