luogu7717「EZEC-10」序列题解

想了想还是把这题单独拿出来了。

Solution

由于异或运算满足交换律和结合律，所以我们对于限制 $(x_i,y_i,z_i)$ ，连边 $(x_i, y_i)$ ，权值为 $z_i$ ，这样只要确定了连通块中一个点，其他点的点权也可以确定。

会构成若干连通块，对于每个连通块分别考虑。

随便钦定一个点为根，进行 $\text{DFS}$ 得到每个点 $x$ 与根的关系 $d_x$ ，满足 $a_{root} \oplus a_x = d_x$ 。

先把存在环且不合法的情况判掉，然后我们把 $d_x$ 插入 0-1 Trie。

考虑 Trie 树上 $\text{DFS}$ 。设 $f(x,\delta,k)$ 为在节点 $x$ ，考虑了前 $\delta$ 位，此时最大值为 $k$ 的方案数。

唯一的限制在于每个数必须在 $[0,K]$ 之间。

规定左儿子为 $0$ 儿子，右儿子为 $1$ 儿子。

如果节点 $x$ 同时存在左右儿子，那么无论根取什么值，最大值一定会加上 $2^{\delta}$ ，所以

f(x,\delta,k) = f\Big(son_0(x),\delta-1,k+2^{\delta}\Big) + f\Big(son_1(x),\delta-1,k+2^{\delta}\Big)

如果只有左儿子或右儿子，那么

只有左儿子且 $k+2^{\delta} \le K$ 。那么如果这一位放 $1$ ，那么方案就是 $f\Big(son_0(x),\delta-1,k+2^{\delta}\Big)$ ，否则无论后面放什么都不会超过 $k$ ，方案数 $2^{\delta}$ 。
只有左儿子且 $k+2^{\delta} > K$ 。那么只能放 $1$ ，方案数 $f\Big(son_0(x),\delta-1,k\Big)$

只有右儿子的情况类似。

特判孤点，方案是 $k+1$ ，直接乘起来。

1
#include<bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define SET(a,b) memset(a,b,sizeof(a))
5
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
6
#define per(i,j,k) for(int i=(j);i>=(k);--i)
7
int read() {
8
    int a=0, f=1; char c=getchar();
9
    while(!isdigit(c)) {
10
        if(c=='-') f=-1;
11
        c=getchar();
12
    }
13
    while(isdigit(c)) a=a*10+c-'0', c=getchar();
14
    return a*f;
15
}
16
const int N=5e5+5, mod=1e9+7;
17
int n, m, K, ans=1, d[N], deg[N];
18
bool vis[N];
19
struct Gr {
20
    int tot, h[N], to[N<<1], nxt[N<<1], w[N<<1];
21
    void add(int x,int y,int z) {
22
        to[++tot]=y, w[tot]=z, nxt[tot]=h[x], h[x]=tot;
23
    }
24
} G;
25
namespace Trie {
26
    int cnt=1, t[N*29][2];
27
    void init() {
28
        rep(i,0,cnt) t[i][0]=t[i][1]=0;
29
        cnt=1;
30
    }
31
    void insert(int S) {
32
        int x=1;
33
        for(int i=29;~i;--i) {
34
            int a=(S>>i)&1;
35
            if(!t[x][a]) t[x][a]=++cnt;
36
            x=t[x][a];
37
        }
38
    }
39
    int Dfs(int x,int d,int k) {
40
        if(k>K) return 0;
41
        if(!t[x][0]&&!t[x][1]) return 1;
42
        if(t[x][0]&&t[x][1]) return Dfs(t[x][0],d-1,k+(1<<d))+Dfs(t[x][1],d-1,k+(1<<d));
43
        if(t[x][0]) {
44
            if(k+(1<<d)<=K) return (1<<d)+Dfs(t[x][0],d-1,k+(1<<d));
45
            return Dfs(t[x][0],d-1,k);
46
        } else {
47
            if(k+(1<<d)<=K) return (1<<d)+Dfs(t[x][1],d-1,k+(1<<d));
48
            return Dfs(t[x][1],d-1,k);
49
        }
50
    }
51
};
52
void dfs(int x) {
53
    vis[x]=1;
54
    Trie::insert(d[x]);
55
    for(int i=G.h[x];i;i=G.nxt[i]) {
56
        int y=G.to[i], z=G.w[i];
57
        if(d[y]!=-1&&(d[x]^z^d[y])!=0) {
58
            puts("0");
59
            exit(0);
60
        }
61
        d[y]=d[x]^z;
62
        if(!vis[y]) dfs(y);
63
    }
64
}
65
signed main() {
66
    n=read(), m=read(), K=read();
67
    rep(i,1,m) {
68
        int x=read(), y=read(), z=read();
69
        G.add(x,y,z), G.add(y,x,z);
70
        ++deg[x], ++deg[y];
71
    }
72
    SET(d,-1);
73
    for(int i=1;i<=n;++i) {
74
        if(vis[i]) continue;
75
        if(!deg[i]) { (ans*=K+1)%=mod; continue; }
76
        Trie::init();
77
        d[i]=0;
78
        dfs(i);
79
        (ans*=Trie::Dfs(1,29,0))%=mod;
80
    }
81
    printf("%lld\n",ans);
82
}

Nanami^2

Solution

觉得这篇文章怎么样？

分享这篇文章

评论区

搜索结果

标签

分类

搜索结果

标签

分类

Solution

觉得这篇文章怎么样？

分享这篇文章

评论区