[ABC213G] Connectivity 2 Solution

[ABC213G] Connectivity 2 Solution更好的阅读体验戳此进入题面SolutionCodeUPD

更好的阅读体验戳此进入

题面

$n$ $m$ $0$ $2^m$ $k \in [2, n]$ $k$ $1$ $998244353$ 取模。

Solution

对于 FZT（子集计数）的更具体说明可以参考 FZT - 子集计数学习笔记。

$S$ 为二进制状态，表示某个点是否钦定。

$F(S)$ $S$ $G(S)$ $S$ 可以产生的子图数量。

$cnt_S$ $S$ $G(S) = 2^{cnt_S}$ $O(m2^n)$ ，可以接受。

$F$ ，不难想到（错误的）转移为：

F (S) = G (S) - \sum_{T ⊊ S} F (T) \times G (S \oplus T)

$S$ $G(S)$ $S$ $T$ $T$ $S$ $T$ $T$ $S$ $T$ $S \oplus T$ $G(S \oplus T)$ $O(3^n)$ ，可以接受。

这个东西是假的 $S$ $1$ 。

于是转移优化为：

F (S) = G (S) - \sum_{1 \in T ⊊ S} F (T) \times G (S \oplus T)

$1$ $3$ $1$ $0$ $1e8$ 级别，可以接受，且更易于实现。

$F(0) = G(0) = 1$ ，也就是所有点都不选的时候认为所有边都不选也是一种方案。

$i$ $ans_i$ $S = 2^n - 1$ ，也就是全集，显然有：

a n s_{i} = \sum_{T \subseteq S} F (T) \times G (S \oplus T) \times [T \land 2^{i - 1}] \times [T \land 1]

$O(n2^n)$ 。

$O((m + n)2^n + 3^n)$ ，卡的比较满，但是有三秒，显然可以通过。

$Smx$ $Smx = 2^{n} - 1$ ，然后枚举的过程就是 for(int S = Smx; S; S = (S - 1) & Smx)，具体证明这里不再赘述，可以网上直接搜一下。

$2^n$ $O(3^n)$ $k$ $(k + 1)^n$ $O(3^n)$ 。

Code


xxxxxxxxxx
88
1
#define _USE_MATH_DEFINES
2
#include <bits/stdc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12

13
mt19937 rnd(random_device{}());
14
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
15
bool rnddd(int x){return rndd(1, 100) <= x;}
16

17
typedef unsigned int uint;
18
typedef unsigned long long unll;
19
typedef long long ll;
20
typedef long double ld;
21

22
#define MOD (ll)(998244353ll)
23
#define MAX_STATUS (150000)
24
#define EXIST(x) (S & (1 << ((x) - 1)))
25

26
template < typename T = int >
27
inline T read(void);
28

29
int N, M;
30
struct Edge{
31
    Edge* nxt;
32
    int to;
33
    OPNEW;
34
}ed[2100];
35
ROPNEW(ed);
36
Edge* head[20];
37
ll F[MAX_STATUS], G[MAX_STATUS];
38
ll pow2[500];
39
ll ans[20];
40

41
int main(){
42
    pow2[0] = 1;
43
    for(int i = 1; i <= 300; ++i)pow2[i] = pow2[i - 1] * 2 % MOD;
44
    N = read(), M = read();
45
    const int Smx = (1 << N) - 1;
46
    for(int i = 1; i <= M; ++i){
47
        int s = read(), t = read();
48
        head[s] = new Edge{head[s], t};
49
    }F[0] = G[0] = 1;
50
    for(int S = Smx; S; S = (S - 1) & Smx){
51
        int cnt(0);
52
        for(int p = 1; p <= N; ++p)
53
            if(EXIST(p))
54
                for(auto i = head[p]; i; i = i->nxt)
55
                    if(EXIST(SON))++cnt;
56
        G[S] = pow2[cnt];
57
    }
58
    for(int S = 1; S <= Smx; ++S){
59
        for(int T = (S - 1) & S; T; T = (T - 1) & S)
60
            if(T & 1)
61
                (F[S] += F[T] * G[S ^ T] % MOD) %= MOD;
62
        F[S] = (G[S] - F[S] + MOD) % MOD;
63
    }
64
    for(int i = 2; i <= N; ++i)
65
        for(int S = Smx; S; S = (S - 1) & Smx)
66
            if(EXIST(i) && EXIST(1))(ans[i] += F[S] * G[S ^ Smx] % MOD) %= MOD;
67
    for(int i = 2; i <= N; ++i)printf("%lld\n", ans[i]);
68
    // for(int S = Smx; S; S = (S - 1) & Smx)
69
    //     cout << "G[" << bitset < 6 >(S) << "] = " << G[S] << ", F = " << F[S] << endl;
70
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
71
    return 0;
72
}
73

74
template < typename T >
75
inline T read(void){
76
    T ret(0);
77
    int flag(1);
78
    char c = getchar();
79
    while(c != '-' && !isdigit(c))c = getchar();
80
    if(c == '-')flag = -1, c = getchar();
81
    while(isdigit(c)){
82
        ret *= 10;
83
        ret += int(c - '0');
84
        c = getchar();
85
    }
86
    ret *= flag;
87
    return ret;
88
}

UPD

update-2022_12_05 初稿