CF1218D Xor Spanning Tree

发表于 | 阅读数

给个仙人掌图，只有42个环。求最小异或生成树，以及方案数。

因为是异或，无法贪心。一定是在每个环上去掉一条边。

答案就是$sum_{xor}\oplus w_1\oplus w_2…\oplus w_k$

$w_i$表示第$i$个环去掉的边。

由于边权$<2^{17}$,$f_j(i)$表示第j个环上权值为$i$的数量。考虑生成函数$(f_1(0)x^0+f_1(1)x^1..f_1(2^{17}-1)x^{2^{17}-1})\times.. (f_k(0)x^0+f_k(1)x^1..f_k(2^{17}-1)x^{2^{17}-1})\times (x^{sum_{xor}})$

最后遍历一下即可。

  • 复杂度$O(42\times 17 \times 2^{17})$
  • 做$FWT$,类似与$NTT$，都先转为点值表示，最后变成多项式。可以减少不必要的常数
代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1 << 17;

int mod = 1e9 + 7; // 998244353
int read()
{
    int x = 0, F = 1;
    char d = getchar();
    while (d < '0' || d > '9')
    {
        if (d == '-')
            F = -1;
        d = getchar();
    }
    while (d >= '0' && d <= '9')
        x = (x << 1) + (x << 3) + d - '0', d = getchar();
    return x * F;
}
int qpow(int a, int x, int mo)
{
    int res = 1;
    while (x)
    {
        if (x & 1)
            res = 1ll * res * a % mo;
        x >>= 1;
        a = 1ll * a * a % mo;
    }
    return res;
}
int inc(int x, int y, int mo)
{
    if (y < 0)
        y += mo;
    if (x + y >= mo)
        x -= mo;
    return x + y;
}
int Inv2;
void FWT(int *A, int n, int op, int t) //t=1 or t=2 and t=3 xor
{
    for (int i = 2; i <= n; i <<= 1)
    {
        for (int j = 0, mid = i >> 1; j < n; j += i)
            for (int k = 0; k < mid; k++)
            {

                if (t == 1)
                    A[j + mid + k] = inc(A[j + mid + k], A[j + k] * op, mod);
                else if (t == 2)
                    A[j + k] = inc(A[j + k], A[j + mid + k] * op, mod);
                else if (t == 3)
                {
                    int x = A[j + k], y = A[j + mid + k];
                    if (op == 1)
                        A[j + k] = (x + y) % mod, A[j + mid + k] = (x - y + mod) % mod;
                    else
                        A[j + k] = 1ll * Inv2 * (x + y) % mod, A[j + mid + k] = 1ll * Inv2 * (x - y + mod) % mod;
                }
            }
    }
}
void FWTX(int *A, int *B, int n, int t)
{
    Inv2 = qpow(2, mod - 2, mod);
    FWT(B, n, 1, t);

    for (int i = 0; i < n; ++i)
        A[i] = 1ll * A[i] * B[i] % mod;
    //FWT(A, n, -1, t);
}

vector<pii> g[N];
int dfn[N];
int vis[N], fa[N], fw[N];
int a[N], b[N], g1[N], g2[N];
void dfs(int x)
{
    vis[x] = 1;
    dfn[x] = dfn[fa[x]] + 1;
    for (pii now : g[x])
    {
        int v = now.first;
        int w = now.second;
        if (v == fa[x])
            continue;
        if (vis[v] && dfn[v] < dfn[x])
        {
            memset(a, 0, sizeof(a));
            memset(b, 0, sizeof(b));

            int sum = w;
            int f = x;
            a[w]++;
            b[w]++;
            while (f != v)
                a[fw[f]]++, b[fw[f]]++, f = fa[f];
            mod = 1e9 + 7;
            FWTX(g1, a, 1 << 17, 3);
            mod = 998244353;
            FWTX(g2, b, 1 << 17, 3);
        }
        else if (vis[v] == 0)
        {
            fa[v] = x;
            fw[v] = w;
            dfs(v);
        }
    }
}
int main()
{
    int n = read(), m = read();
    int sum = 0;
    for (int i = 1; i <= m; i++)
    {
        int u = read(), v = read(), w = read();
        g[u].push_back(mk(v, w));
        g[v].push_back(mk(u, w));
        sum ^= w;
    }
    g1[sum] = 1;
    g2[sum] = 1;

    mod = 1e9 + 7;
    Inv2 = qpow(2, mod - 2, mod);
    FWT(g1, 1 << 17, 1, 3);
    mod = 998244353;
    Inv2 = qpow(2, mod - 2, mod);
    FWT(g2, 1 << 17, 1, 3);

    dfs(1);
    mod = 1e9 + 7;
    Inv2 = qpow(2, mod - 2, mod);
    FWT(g1, 1 << 17, -1, 3);
    mod = 998244353;
    Inv2 = qpow(2, mod - 2, mod);
    FWT(g2, 1 << 17, -1, 3);
    for (int i = 0; i < (1 << 17); i++)
    {
        if (g1[i] || g2[i])
        {
            printf("%d %d\n", i, g1[i]);
            return 0;
        }
    }
}