제출 #704604

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
704604		Nursik	W (RMI18_w)	C++14	0 / 100	1091 ms	52336 KiB

w

#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 + 10, maxm = 3e5 + 1;
const ll mod = 1e9 + 7, cmod = 998244353, inf = 1e9, blcok = 400, p2 = 31;
const ld eps = 1e-9;

int a[maxn];
int cnt[maxn];
int dp[maxm][(1 << 5)];
int isbits[maxm];
int fact[maxn];
vector<int> states, 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 f(int mask, int mask2, int c){
    int nbits = __builtin_popcount((mask ^ mask2));
    int bits = isbits[mask2];
    return cnk(c - nbits + bits - 1, bits - 1);
}
int n;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); 
    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        cnt[a[i]] += 1;
    }
    fact[0] = 1;
    for (int i = 1; i <= n + n; ++i){
        fact[i] = fact[i - 1] * 1ll * i % mod;
    }
    states.pb(0); isbits[0] = 0;
    go[0].pb(2);
    go[0].pb(8);
    go[0].pb(10);
    
    states.pb(2); isbits[2] = 1;
    go[2].pb(2);
    go[2].pb(3);
    go[2].pb(10);
    go[2].pb(11);
    
    states.pb(8); isbits[8] = 1;
    go[8].pb(8);
    go[8].pb(10);
    go[8].pb(24);
    go[8].pb(26);
    
    states.pb(3); isbits[3] = 2;
    go[3].pb(3);
    go[3].pb(11);
    
    states.pb(24); isbits[24] = 2;
    go[24].pb(24);
    go[24].pb(26);
    
    states.pb(10); isbits[10] = 2;
    go[10].pb(1);
    go[10].pb(24);
    go[10].pb(30);
    go[10].pb(31);
    go[10].pb(23);
    go[10].pb(14);
    go[10].pb(15);
    go[10].pb(11);

    states.pb(26); isbits[26] = 3;
    go[26].pb(26);
    go[26].pb(27);
    go[26].pb(30);
    go[26].pb(31);

    states.pb(11); isbits[11] = 3;
    go[11].pb(11);
    go[11].pb(27);
    go[11].pb(15);
    go[11].pb(31);

    states.pb(14); isbits[14] = 1;
    go[14].pb(31);
    go[14].pb(15);
    go[14].pb(30);

    states.pb(27); isbits[27] = 4;
    go[27].pb(27);
    go[27].pb(31);

    states.pb(30); isbits[30] = 1;
    go[30].pb(30);
    go[30].pb(31);

    states.pb(15); isbits[15] = 1;
    go[15].pb(15);
    go[15].pb(31);

    states.pb(31); isbits[31] = 2;
    go[31].pb(31);

    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 = (int)v.size();
    for (int i = 1; i <= n; ++i){
        a[i] = v[i - 1];
    }
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i){
        if (cnt[a[i]] > 0){
            for (auto it : states){
                if (dp[i - 1][it] > 0){
                    for (auto to : go[it]){
                        int nj = to;
                        dp[i][nj] = (dp[i][nj] + dp[i - 1][it] * 1ll * f(it, to, cnt[a[i]]) % mod) % mod;
                    }
                }
            }
        }
    }
    cout << dp[n][(1 << 5) - 1];
}
/*
00000 - 0
01000 - 2
00010 - 8
11000 - 3
00011 - 24
01010 - 10
01011 - 26
11010 - 11
11011 - 27
01111 - 30
11110 - 15
11111 - 31
*/

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