Submission #557931

#	Time	Username	Problem	Language	Result	Execution time	Memory
557931		FatihSolak	W (RMI18_w)	C++17	55 / 100	348 ms	23244 KiB

w

#include <bits/stdc++.h>
#define N 300005
using namespace std;
const int mod = 1e9 + 7;
long long fact[N];
long long ifact[N];
long long binpow(long long a,long long b){
	long long ret = 1;
	while(b){
		if(b & 1)
			ret = ret*a%mod;
		a = a*a%mod;
		b >>= 1;
	}
	return ret;
}
long long C(int n,int r){
	return fact[n] * ifact[r]%mod*ifact[n-r]%mod;
}
long long val[N][5];
void solve(){
	int n;
	cin >> n;
	vector<int> tmp;
	map<int,int> cnt;
	for(int i = 1;i<=n;i++){
		int x;
		cin >> x;
		tmp.push_back(x);
		cnt[x]++;
	}
	if(n <= 11){
		sort(tmp.begin(),tmp.end());
		int ans = 0;
		do{
			int cnt = 0;
			int last = -1;
			for(int i = 1;i<n;i++){
				if(tmp[i] == tmp[i-1])continue;
				int now = (tmp[i] > tmp[i-1]);
				if(now != last){
					if(last == -1 && now == 1){
						break;
					}
					cnt++;
					last = now;
				}
			}
			if(cnt == 4){
				ans++;
			}

		}while(next_permutation(tmp.begin(),tmp.end()));
		cout << ans << endl;
		return;
	}
	vector<int> v;
	for(auto u:cnt)
		v.push_back(u.second);
	if(cnt.size() == 2){
		if(v[0] < 2 || v[1] < 3){
			cout << 0;
			return;
		}
		cout << C(v[0]-2+1,1) *C(v[1]-3+2,2) %mod;
		return;
	}
	/*
	for(int i = 2;i<=n;i++){
		val[i][1] = 1;
	}
	for(int i = 3;i<=n;i++){
		val[i][2] = (binpow(2,i-1) - 2 + mod)%mod;
	}
	for(int i = 4;i<=n;i++){
		//val[n][3] = (3^n - 2^(n+2) - 2n + 11)/4
		val[i][3] = (binpow(3,i) - binpow(2,i+2) - 2*i + 11 + 2*mod)%mod*binpow(4,mod-2)%mod;
		//cout << i << " " << val[i][3] << endl;
	}*/
	for(int i = n;i<=n;i++){
		for(int j = 2;j<=i-3;j++){
			val[i][4] = (val[i][4] + C(i-1,j-1) * 
			(   (binpow(3,i-j) - binpow(2,i-j+1) - 2 * (i-j) + 3 + 5ll*mod  )%mod       )%mod)%mod;
		}

		/*
		long long add = 0;

		add = 0;
		add = (binpow(4,n-1));
		for(int j = 0;j<1;j++){
			add = (add - C(i-1,j)*binpow(3,i-j) + mod)%mod;
		}
		for(int j = i-4;j<i;j++){
			add = (add - C(i-1,j)*binpow(3,i-j) + mod)%mod;
		}
		add = (add * binpow(3,mod-2))%mod;
		val[i][4] = (val[i][4] + add)%mod;


		add = 0;
		add = (binpow(3,n-1));
		for(int j = 0;j<1;j++){
			add = (add - C(i-1,j)*binpow(2,i-j) + mod)%mod;
		}
		for(int j = i-4;j<i;j++){
			add = (add - C(i-1,j)*binpow(2,i-j) + mod)%mod;
		}
		val[i][4] = (val[i][4] + add)%mod;

		add = 0;
		add = (binpow(3,n-1));
		for(int j = 0;j<1;j++){
			add = (add - C(i-1,j)*binpow(2,i-j) + mod)%mod;
		}
		for(int j = i-4;j<i;j++){
			add = (add - C(i-1,j)*binpow(2,i-j) + mod)%mod;
		}
		val[i][4] = (val[i][4] + add)%mod;
		*/
		val[i][4] = val[i][4]*binpow(2,mod-2) %mod;
		//cout << i << " " << val[i][4] << endl;
	}
	cout << val[n][4] << endl;

}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	#ifdef Local
		freopen("in.txt","r",stdin);
		freopen("out.txt","w",stdout);
	#endif
	fact[0] = ifact[0]= 1;
	for(int i = 1;i<N;i++){
		fact[i] = fact[i-1] * i %mod;
		ifact[i] = binpow(fact[i],mod-2);
	}
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
	#ifdef Local
		cout << endl << fixed << setprecision(2) << 1000.0*clock()/CLOCKS_PER_SEC << " milliseconds.";
	#endif
}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 5 / 50