oj.uz

답안 #709679

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
709679 2023-03-14T07:28:33 Z Nursik W (RMI18_w) C++14
35 / 100
 600 ms 64676 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;

int n;
int a[maxn];
ll fact[maxn];
int cnt[maxn];
ll dp[maxn][(1 << 5)];
vector<pair<int, pair<int, int>>> go[maxn];
ll bp(ll a, ll n){
    ll res = 1;
    while (n > 0){
        if (n & 1){
            res *= a;
        }
        a *= a, n >>= 1;
        a %= mod, res %= mod;
    }
    return res;
}
ll cnk(int n, int k){
    if (n < k)
        return 0;
    return fact[n] * bp(fact[k], mod - 2) % mod * bp(fact[n - k], mod - 2) % mod;
}
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(3, 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;
    fact[0] = 1;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        cnt[a[i]] += 1;
        fact[i] = fact[i - 1] * i % mod;
    }
    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][0] = 1;
    for (int i = 1; i <= n; ++i){
        if (cnt[a[i]] > 0){
            for (auto it : masks){
                if (dp[i - 1][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[i][gmask] = (dp[i][gmask] + dp[i - 1][it] * cnk(cnt[a[i]] - nbits + allbits - 1, allbits - 1) % mod) % mod;
                    }
                }
            }
            cnt[a[i]] = 0;
        }
    }
    cout << dp[n][(1 << 5) - 1];
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23812 KB Output is correct
2 Correct 15 ms 23812 KB Output is correct
3 Correct 17 ms 24380 KB Output is correct
4 Correct 45 ms 27324 KB Output is correct

Subtask #2
15.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 23776 KB Output is correct
2 Correct 21 ms 24136 KB Output is correct
3 Correct 246 ms 35876 KB Output is correct
4 Execution timed out 818 ms 54492 KB Time limit exceeded
5 Execution timed out 1075 ms 61444 KB Time limit exceeded
6 Execution timed out 1076 ms 64364 KB Time limit exceeded

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 23808 KB Output isn't correct
2 Incorrect 14 ms 23764 KB Output isn't correct
3 Incorrect 13 ms 23812 KB Output isn't correct
4 Incorrect 14 ms 23892 KB Output isn't correct
5 Incorrect 12 ms 23856 KB Output isn't correct
6 Incorrect 49 ms 25080 KB Output isn't correct
7 Incorrect 59 ms 25592 KB Output isn't correct
8 Incorrect 24 ms 25424 KB Output isn't correct
9 Incorrect 47 ms 26508 KB Output isn't correct
10 Execution timed out 1087 ms 64676 KB Time limit exceeded