全国互虐 TEST 5.31【魔法】

首先 可以证明
一条路径是由一大堆环和一条从1到某个点的链组成的
对于图上的所有环 对于某条链 都可以选或不选
即环和链的选择是独立的
如果现在有cnt个本质不同的环
和ccnt个本质不同的链
答案就是ccnt * 2^(cnt) – 1
因为对于每条链 所有环都可以选或不选
然后减掉0的情况

所谓本质相同的环a,b
就是把a任意异或其他环 得出的答案集合A
和把b任意异或其他环 得出的答案集合B是相同的
则他们本质相同
排除这种情况 只要对他们进行高斯消元 排除掉0的值就行了

本质相同的链的定义类似 两条链在环中进行高斯消元后 如果答案一样 则本质相同

然后就可以算出ans了

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
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <sstream>
using namespace std;
typedef long long ll;
typedef long double ld;

const ll maxn = 100005;

struct line
{
  ll to, next, v;
}li[maxn];

struct Line
{
  ll fr, to, v;
}L[maxn];

ll a[maxn], v[maxn], c[maxn], b[maxn], n, m, q, be[maxn], l, ans[maxn], Q[maxn], f[maxn], cnt, ccnt, r[maxn];
set<ll> s;

void dfs(ll now, ll la)
{
  f[now] = la;
  c[++ccnt] = la;
  v[now] = 1;
  for (ll i = be[now]; i; i = li[i].next)
  {
    ll to = li[i].to;
    if (v[to]) a[++cnt] = f[now] ^ f[to] ^ li[i].v;
    else dfs(to, la ^ li[i].v);
  }  
}

ll re(ll v)
{
  for (ll i = 62; i >= 0; --i)
    if (v & (1LL << i)) v ^= r[i];
  return v;
}

ll calc()
{
  for (ll i = 1; i <= cnt; ++i) b[i] = 0;
  for (ll i = 62; i >= 0; --i)
  {
    ll p = 0;
    for (ll j = 1; j <= cnt; ++j)
      if (!b[j] && (a[j] & (1LL << i)))
      {
        p = j;
        break;          
      }
    if (!p)
    {
      r[i] = 0;
      continue;      
    }
    r[i] = a[p]; b[p] = 1;
    for (ll j = 1; j <= cnt; ++j)
      if (p != j && a[j] & (1LL << i)) a[j] ^= a[p];
  }
  ll cur = 0;
  for (ll i = 1; i <= cnt; ++i)
    if (a[i]) a[++cur] = a[i];
  cnt = cur;
  s.clear();
  cur = 0;
  for (ll i = 1; i <= ccnt; ++i)
  {
    ll t = re(c[i]);
    if (s.find(t) == s.end())
    {
      s.insert(t);
      c[++cur] = c[i];          
    }
  }
  ccnt = cur;
  return ccnt * (1LL << cnt) - 1;
}

void makeline(ll fr, ll to, ll v)
{
  ++l;
  li[l].next = be[fr];
  be[fr] = l;
  li[l].to = to;
  li[l].v = v;    
}

int main()
{
  scanf("%lld%lld%lld", &n, &m, &q);
  for (ll i = 1; i <= m; ++i)
    scanf("%lld%lld%lld", &L[i].fr, &L[i].to, &L[i].v);
  for (ll i = 0; i < q; ++i) scanf("%lld", &Q[i]), b[Q[i]] = 1;
  for (ll i = 1; i <= m; ++i)
    if (!b[i])
    {
      makeline(L[i].fr, L[i].to, L[i].v);
      makeline(L[i].to, L[i].fr, L[i].v);
    }
  dfs(1, 0);
  ans[q] = calc();
  for (ll i = q - 1; i >= 0; --i)
  {
    ll fr = L[Q[i]].fr, to = L[Q[i]].to, V = L[Q[i]].v;
    makeline(fr, to, V);
    makeline(to, fr, V);
    if (v[fr] && v[to]) a[++cnt] = f[fr] ^ f[to] ^ V;
    else if (v[fr]) dfs(to, f[fr] ^ V);
    else if (v[to]) dfs(fr, f[to] ^ V);
    ans[i] = calc();
  }
  for (ll i = 0; i <= q; ++i) printf("%lld\n", ans[i]);
}

全国互虐 TEST 5.31【魔法】》上有3条评论

发表评论