Submission #1222344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222344		_callmelucian	Amusement Park (CEOI19_amusementpark)	C++17	0 / 100	3 ms	6472 KiB

amusementpark

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;
using pl = pair<ll,ll>;
using pii = pair<int,int>;
using tpl = tuple<int,int,int>;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

vector<int> adj[18];
vector<pii> dp[1 << 18];
int bitmask[18], good[1 << 18][18];

const int MOD = 998'244'353;
const int inv2 = 499'122'177;

int add (int a, int b) { return a + b - (a + b < MOD ? 0 : MOD); }
int sub (int a, int b) { return a - b + (a - b >= 0 ? 0 : MOD); }
int mul (int a, int b) { return 1LL * a * b % MOD; }

int binpow (int a, int b) {
    int ans = 1;
    for (; b; b >>= 1, a = mul(a, a))
        if (b & 1) ans = mul(ans, a);
    return ans;
}

bool getCur (int mask, int pos) {
    return mask >> pos & 1;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, m; cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        a--, b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
        bitmask[a] |= (1 << b);
        bitmask[b] |= (1 << a);
    }
    for (int i = 0; i < n; i++)
        sort(all(adj[i]), greater<int>());

    /// find valid masks & setup mask case
    for (int mask = 0; mask < (1 << n); mask++) {
        bool valid = 1;
        for (int i = 0; i < n; i++)
            if (getCur(mask, i) && (mask & bitmask[i])) { valid = 0; break; }
        if (valid) dp[0].emplace_back(mask, 1);
    }

    for (int mask = 0; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++) {
            int cur = 0;
            for (int j : adj[i])
                if (!(mask & bitmask[j])) cur |= (1 << j);
            good[mask][i] = cur;
        }
    }

    /// run DP
    int ans = 0;
    for (int A = 0; A < (1 << n); A++) {
        if (A) {
            sort(all(dp[A]));
            vector<pii> tmp;
            for (auto [B, val] : dp[A]) {
                if (tmp.size() && tmp.back().first == B)
                    tmp[tmp.size() - 1].second = add(tmp.back().second, val);
                else tmp.emplace_back(B, val);
            }
            swap(dp[A], tmp);
        }

        for (auto [B, val] : dp[A]) {
//            cout << "dp " << bitset<2>(A) << ", " << bitset<2>(B) << " " << val << endl;
            for (int sub = B; sub; sub -= sub & (-sub)) {
                int cur = __builtin_ctz(sub), subFull = (1 << (cur + 1)) - 1;
                int leftNode = B ^ (B & subFull), newNode = bitmask[cur] ^ (bitmask[cur] & (A | (1 << cur)));
                dp[A | (1 << cur)].emplace_back(leftNode | newNode, val);
            }
            if (A == (1 << n) - 1 && B == 0) ans = val;
        }
    }
    cout << mul(mul(ans, inv2), m);

    return 0;
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 12
• Subtask 3: 0 / 23
• Subtask 4: 0 / 21
• Subtask 5: 0 / 37