제출 #1222294

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222294		_callmelucian	Amusement Park (CEOI19_amusementpark)	C++17	42 / 100	3072 ms	628196 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())

bitset<18> bitmask[18];
bitset<1 << 18> valid;
vector<int> adj[18];
map<int,int> cached[1 << 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;
}

void increase (int A, int B, int incr) {
    if (!incr) return;
    if (!cached[A].count(B)) cached[A][B] = 0;
    auto &it = cached[A][B];
    it = add(it, incr);
}

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][b] = bitmask[b][a] = 1;
    }
    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++) {
        valid[mask] = 1;
        for (int i = 0; i < n; i++)
            if (getCur(mask, i) && (bitset<18>(mask) & bitmask[i]).count()) { valid[mask] = 0; break; }
        if (valid[mask]) cached[0][mask] = 1;
    }

    /// run DP
    for (int A = 0; A < (1 << n); A++) {
        // expand B operation only
        for (auto [B, dp] : cached[A]) {
            if (!(A & B)) continue;
//            cout << "1p " << bitset<2>(A) << " " << bitset<2>(B) << " " << dp << "\n";
            int cur = __builtin_ctz(A & B);
            increase(A, B ^ (1 << cur), dp);
            for (int j : adj[cur]) {
                if (getCur(B, j)) break;
                if (!getCur(A, j) && !(bitset<18>(B ^ (1 << cur)) & bitmask[j]).count()) increase(A, B | (1 << j), dp);
            }
        }
        // move B to A operation only
        for (auto [B, dp] : cached[A]) {
            if ((A & B) || !B) continue;
//            cout << "2p " << bitset<2>(A) << " " << bitset<2>(B) << " " << dp << "\n";
            int cur = __builtin_ctz(B);
            increase(A | (1 << cur), B, dp);
        }
    }

    int ans = cached[(1 << n) - 1][0];

//    cout << ans << " ";
    cout << mul(mul(ans, inv2), m);

    return 0;
}

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