結果

問題 No.696 square1001 and Permutation 5
コンテスト
ユーザー rapurasu
提出日時 2018-07-13 10:39:47
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 1 WA * 11
権限があれば一括ダウンロードができます

ソースコード

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