Submission #696761

#	Time	Username	Problem	Language	Result	Execution time	Memory
696761		vjudge1	Amusement Park (CEOI19_amusementpark)	C++17	63 / 100	3090 ms	3412 KiB

amusementpark

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
#define fir first
#define sec second
typedef vector <int> vi;
typedef vector <ll> vl;
template <typename __Tp> void read(__Tp &x) {
    int f = 0; x = 0; char ch = getchar();
    for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = 1;
    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
    if (f) x = -x;
}
template <typename __Tp1, typename ...__Tp2> void read(__Tp1 &x, __Tp2 &...y) { read(x), read(y...); }
template <typename __Tp> void write(__Tp x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x / 10);
    putchar(x % 10 + 48);
}
void write(char ch) { putchar(ch); }
template <typename __Tp1, typename ...__Tp2> void write(__Tp1 x, __Tp2 ...y) { write(x), write(y...); }

const int mod = 998244353;
template <int mod>
struct mint {
    #define fix(x) (((x) % mod + mod) % mod)
    int x;
    mint() { x = 0; }
    template <typename __Tp> mint(__Tp _x) { x = fix(_x); }
    friend mint operator + (mint a, mint b) { return a.x + b.x; }
    friend mint operator - (mint a, mint b) { return a.x - b.x; }
    friend mint operator * (mint a, mint b) { return (ll) a.x * b.x; }
    template <typename __Tp>
    friend mint operator ^ (mint a, __Tp b) {
        mint ans = 1;
        while (b) {
            if (b & 1) ans *= a;
            a *= a, b >>= 1;
        }
        return ans;
    }
    friend mint operator / (mint a, mint b) { return a * (b ^ (mod - 2)); }
    friend mint & operator += (mint & a, mint b) { return a = a + b; }
    friend mint & operator -= (mint & a, mint b) { return a = a - b; }
    friend mint & operator *= (mint & a, mint b) { return a = a * b; }
    template <typename __Tp>
    friend mint & operator ^= (mint & a, __Tp b) { return a = a ^ b; }
    friend mint & operator /= (mint & a, mint b) { return a = a / b; }
    #undef fix
};
typedef mint <mod> mi;
int n, m, e[20], vld[1 << 18], popcnt[1 << 18], lg[1 << 18];
mi f[1 << 18];

int main() {
    read(n, m);
    for (int i = 1; i <= m; ++i) {
        int u, v; read(u, v), --u, --v;
        e[u] |= (1 << v), e[v] |= (1 << u);
    }
    int S = (1 << n) - 1;
    for (int i = 0; i < n; ++i) lg[1 << i] = i;
    vld[0] = 1;
    for (int s = 1; s <= S; ++s) {
        int i = lg[s & -s];
        popcnt[s] = popcnt[s & (s - 1)] + 1;
        vld[s] = vld[s & (s - 1)] & !(e[i] & s);
    }
    f[0] = 1;
    for (int s = 1; s <= S; ++s)
        for (int t = s; t; t = (t - 1) & s)
            if (vld[t]) f[s] += f[s ^ t] * (popcnt[t] & 1 ? 1 : -1);
    mi ans = f[S] * m / 2;
    write(ans.x, '\n');
    return 0;
}

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