| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 709689 |
2023-03-14T07:45:46 Z |
Nursik |
W (RMI18_w) |
C++14 |
|
130 ms |
7584 KB |
#include <iostream>
#include <fstream>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <string>
#include <cmath>
#include <cassert>
#include <ctime>
#include <algorithm>
#include <sstream>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <iterator>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <stdio.h>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <functional>
#include <complex>
#include <random>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define ld long double
const ll maxn = 1e6 + 1, maxm = 3e4 + 1;
const ll mod = 1e9 + 7, cmod = 998244353, inf = 1e9, block = 5000, p2 = 31, bit = 30;
const ld eps = 1e-9;
ll cnk(int n, int k){
if (n < k)
return 0;
if (k == 0){
return 1;
}
if (k == 1){
return n;
}
if (k == 2){
return n * 1ll * (n - 1) / 2ll;
}
if (k == 3){
return n * 1ll * (n - 1) * (n - 2) / 6ll;
}
}
int n;
int a[maxn];
ll fact[maxn];
int cnt[maxn];
ll dp[(1 << 5)];
vector<pair<int, pair<int, int>>> go[(1 << 5)];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
vector<int> masks;
/*
00000 - 0
01000 - 2
00010 - 8
11000 - 3
00011 - 24
01010 - 10
11010 - 11
01011 - 26
11011 - 27
01110 - 14
11110 - 15
01111 - 30
11111 - 31
*/
masks.pb(0);
masks.pb(2);
masks.pb(8);
masks.pb(3);
masks.pb(24);
masks.pb(10);
masks.pb(11);
masks.pb(26);
masks.pb(27);
masks.pb(14);
masks.pb(15);
masks.pb(30);
masks.pb(31);
go[0].pb(mp(2, mp(1, 1)));
go[0].pb(mp(8, mp(1, 1)));
go[0].pb(mp(10, mp(2, 2)));
go[2].pb(mp(2, mp(1, 0)));
go[2].pb(mp(10, mp(2, 1)));
go[2].pb(mp(3, mp(2, 1)));
go[2].pb(mp(11, mp(3, 2)));
go[8].pb(mp(8, mp(1, 0)));
go[8].pb(mp(10, mp(2, 1)));
go[8].pb(mp(24, mp(2, 1)));
go[8].pb(mp(26, mp(3, 2)));
go[10].pb(mp(10, mp(2, 0)));
go[10].pb(mp(11, mp(3, 1)));
go[10].pb(mp(26, mp(3, 1)));
go[10].pb(mp(30, mp(2, 2)));
go[10].pb(mp(31, mp(3, 3)));
go[10].pb(mp(27, mp(4, 2)));
go[10].pb(mp(14, mp(1, 1)));
go[10].pb(mp(15, mp(2, 2)));
go[3].pb(mp(3, mp(2, 0)));
go[3].pb(mp(11, mp(3, 1)));
go[24].pb(mp(24, mp(2, 0)));
go[24].pb(mp(26, mp(3, 1)));
go[26].pb(mp(26, mp(3, 0)));
go[26].pb(mp(30, mp(2, 1)));
go[26].pb(mp(27, mp(4, 1)));
go[26].pb(mp(31, mp(3, 2)));
go[11].pb(mp(11, mp(3, 0)));
go[11].pb(mp(15, mp(2, 1)));
go[11].pb(mp(27, mp(4, 1)));
go[11].pb(mp(31, mp(3, 2)));
go[27].pb(mp(27, mp(4, 0)));
go[27].pb(mp(31, mp(3, 1)));
go[14].pb(mp(31, mp(2, 2)));
go[14].pb(mp(30, mp(1, 1)));
go[14].pb(mp(15, mp(1, 1)));
go[15].pb(mp(15, mp(1, 0)));
go[15].pb(mp(31, mp(2, 1)));
go[30].pb(mp(30, mp(1, 0)));
go[30].pb(mp(31, mp(2, 1)));
go[31].pb(mp(31, mp(2, 0)));
cin >> n;
for (int i = 1; i <= n; ++i){
cin >> a[i];
cnt[a[i]] += 1;
}
sort(a + 1, a + n + 1);
vector<int> v;
for (int i = 1; i <= n; ++i){
if (a[i] != a[i - 1]){
v.pb(a[i]);
}
}
n = 0;
for (auto it : v){
a[++n] = it;
}
dp[0] = 1;
reverse(masks.begin(), masks.end());
for (int i = 1; i <= n; ++i){
if (cnt[a[i]] > 0){
for (auto it : masks){
if (dp[it] > 0){
ll x = dp[it];
dp[it] = 0;
for (auto msk2 : go[it]){
pair<int, pair<int, int>> cur = msk2;
int gmask = cur.f;
int allbits = cur.s.f;
int nbits = cur.s.s;
dp[gmask] = (dp[gmask] + x * cnk(cnt[a[i]] - nbits + allbits - 1, allbits - 1) % mod) % mod;
}
}
}
cnt[a[i]] = 0;
}
}
cout << dp[(1 << 5) - 1];
}
Compilation message
w.cpp: In function 'long long int cnk(int, int)':
w.cpp:61:1: warning: control reaches end of non-void function [-Wreturn-type]
61 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
5 ms |
460 KB |
Output is correct |
| 4 |
Correct |
20 ms |
1516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
12 ms |
4548 KB |
Output is correct |
| 4 |
Correct |
37 ms |
5284 KB |
Output is correct |
| 5 |
Correct |
77 ms |
4276 KB |
Output is correct |
| 6 |
Correct |
112 ms |
7584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
2 ms |
340 KB |
Output is correct |
| 7 |
Correct |
4 ms |
724 KB |
Output is correct |
| 8 |
Correct |
12 ms |
1108 KB |
Output is correct |
| 9 |
Correct |
25 ms |
1096 KB |
Output is correct |
| 10 |
Correct |
130 ms |
7584 KB |
Output is correct |
