Submission #557887

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
557887	2022-05-06T09:11:35 Z	FatihSolak	W (RMI18_w)	C++17	30 / 100	600 ms	32188 KB

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;
	map<int,int> cnt;
	for(int i = 1;i<=n;i++){
		int x;
		cin >> x;
		cnt[x]++;
	}
	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;
	}
	val[4][3] = 5;
	for(int i = 5;i<=n;i++){
		val[i][3] = (val[i-1][3] + val[i-1][2])%mod;
		val[i][3] = (val[i][3] + (binpow(3,i-1) - 3*binpow(2,i-1)%mod + 3 + mod)*binpow(2,mod-2)%mod)%mod;
		//cout << i <<" " << val[i][3] << endl;
	}
	for(int i = 5;i<=n;i++){
		for(int j = 2;j<=i-1;j++){
			val[i][4] = (val[i][4] + C(i-1,j-1) * (val[i-j][2] + val[i-j][3]))%mod;
		}
		val[i][4] = val[i][4] *2 %mod;
	}
	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.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	49 ms	5000 KB	Output is correct
2	Correct	44 ms	4892 KB	Output is correct
3	Correct	46 ms	5128 KB	Output is correct
4	Correct	64 ms	5056 KB	Output is correct

Subtask #2

10.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	46 ms	5036 KB	Output is correct
2	Correct	52 ms	5068 KB	Output is correct
3	Execution timed out	1083 ms	7984 KB	Time limit exceeded
4	Execution timed out	1076 ms	14224 KB	Time limit exceeded
5	Execution timed out	1093 ms	23192 KB	Time limit exceeded
6	Execution timed out	1096 ms	32188 KB	Time limit exceeded

Subtask #3

0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	45 ms	4940 KB	Output isn't correct
2	Incorrect	48 ms	4984 KB	Output isn't correct
3	Incorrect	51 ms	5012 KB	Output isn't correct
4	Incorrect	46 ms	4924 KB	Output isn't correct
5	Incorrect	55 ms	5092 KB	Output isn't correct
6	Incorrect	113 ms	5496 KB	Output isn't correct
7	Incorrect	389 ms	5764 KB	Output isn't correct
8	Execution timed out	1087 ms	9024 KB	Time limit exceeded
9	Execution timed out	1082 ms	12988 KB	Time limit exceeded
10	Execution timed out	1084 ms	31668 KB	Time limit exceeded