| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 557931 |
2022-05-06T10:12:05 Z |
FatihSolak |
W (RMI18_w) |
C++17 |
|
348 ms |
23244 KB |
#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
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
4932 KB |
Output is correct |
| 2 |
Correct |
42 ms |
4936 KB |
Output is correct |
| 3 |
Correct |
48 ms |
5276 KB |
Output is correct |
| 4 |
Correct |
67 ms |
7116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
4984 KB |
Output is correct |
| 2 |
Correct |
43 ms |
4992 KB |
Output is correct |
| 3 |
Correct |
59 ms |
6704 KB |
Output is correct |
| 4 |
Correct |
104 ms |
10816 KB |
Output is correct |
| 5 |
Correct |
231 ms |
16676 KB |
Output is correct |
| 6 |
Correct |
315 ms |
23244 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
4884 KB |
Output is correct |
| 2 |
Incorrect |
43 ms |
4988 KB |
Output isn't correct |
| 3 |
Incorrect |
44 ms |
4980 KB |
Output isn't correct |
| 4 |
Incorrect |
44 ms |
4940 KB |
Output isn't correct |
| 5 |
Incorrect |
46 ms |
4940 KB |
Output isn't correct |
| 6 |
Incorrect |
51 ms |
5224 KB |
Output isn't correct |
| 7 |
Incorrect |
54 ms |
5324 KB |
Output isn't correct |
| 8 |
Incorrect |
81 ms |
5636 KB |
Output isn't correct |
| 9 |
Incorrect |
100 ms |
6120 KB |
Output isn't correct |
| 10 |
Incorrect |
348 ms |
22844 KB |
Output isn't correct |
