首先会做这个题。 https://www.luogu.com.cn/problem/P6846

const int N = 18;

struct Edge {
    int a, b;
    void in() {
        RD(a, b); --a; --b;
        a = _1(a); b = _1(b);
    }
    bool in(int s) {
        return (s&a)&&(s&b);
    }
} E[N*N/2];

Int f[1<<N]; bool bad[1<<N];
int n, m;

int main() {

#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    RD(n, m); REP(i, m) E[i].in();

<pre><code>FOR(s, 1, _1(n)) {
    REP(i, m) if (E[i].in(s)) {
        bad[s] = 1;
        break;
    }
}

f[0] = 1; FOR(s, 1, _1(n)) {
    REP_SS(ss, s) if (!bad[ss]) {
        if (count_bits(ss)&amp;amp;1) f[s] += f[s^ss];
        else f[s] -= f[s^ss];
    }
}
cout &amp;lt;&amp;lt; f[_U(n)] * m / 2 &amp;lt;&amp;lt; endl;
</code></pre>

}

然后发现这个题只要加个维。。。

const int N = 15;

Int f[N+2][1<<N], g[N+2][1<<N], fact[N+2];
bool bad[1<<N]; int adj[1<<N];
int n, m, k;

struct Edge {
    int a, b;
    void in() {
        RD(a, b); --a; --b;
        a = _1(a); b = _1(b);
        adj[a] |= b;
    }
    bool in(int s) {
        return (s&a)&&(s&b);
    }
} E[N*(N-1)/2];

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif
    RD(n, m, k); ++k; REP(i, m) E[i].in();
    fact[0] = 1; REP_1(i, k) fact[i] = fact[i-1] * i;

<pre><code>FOR(s, 1, _1(n)) {
    adj[s] |= adj[s^low_bit(s)];
    REP(i, m) if (E[i].in(s)) {
        bad[s] = 1;
        break;
    }
}

g[0][0] = 1; REP_1(i, k) FOR(s, 1, _1(n)) {
    REP_SS(ss, s) if (!bad[ss]) {
        if (count_bits(ss)&amp;amp;1) g[i][s] += g[i-1][s^ss];
        else g[i][s] -= g[i-1][s^ss];
    }
}

f[0][0] = 1; REP_1(i, k) FOR(s, 1, _1(n)) {
    REP_1(ii, i) REP_SS(ss, s) if (!(adj[ss^s]&amp;amp;ss)) {
        Int d = g[ii][ss] * f[i-ii][s^ss];
        if (ii&amp;amp;1) f[i][s] += d;
        else f[i][s] -= d;
    }
}
Int z = 0; REP_1(i, k) z += fact[k] / fact[k-i] * f[i][_U(n)];
cout &amp;lt;&amp;lt; z &amp;lt;&amp;lt; endl;
</code></pre>

}

Posted by xiaodao
Category: 日常