「AGC031F」 Walk on Graph

杂题 / atcoder
Word count: 2k   |   Reading time≈ 9 min

这题针補戳！

Description

有一张 $n$ 个点 $m$ 条边的无向连通图 $G$，每条边有长度 $c_i$ ，有一个人在上面走。
有 $q$ 组询问，每组询问给出 $s_i,t_i,r_i$，表示问你是否存在一条从 $s_i$ 出发到 $t_i$ 结束长度为 $r_i \% Mod$ 的路径。
注意这里的路径长度是 $\sum c_i2^k$。$n,m,q<=50000,Mod<=1000000$ 且 $Mod$ 为奇数。

Solution

首先我们有一个naive的想法，考虑直接搜索，显然我们可以把一个点拆成 $Mod$ 个点，点 $(u,val)$ 表示走到 $u$ 并且当前权值为 $val$，然后可以对着这张图冲一个bfs，当然分肯定是没有的。

直接裸做显然没什么优化的空间，我们考虑把它倒着做，原本我们是求一条 $s \rightarrow t$ 的路径，每一条边的边权为 $c_i2^k$，现在我们变成求一条 $t\rightarrow s$ 的路径，每一条边就变成了把当前的权值乘 2 再加上 $c_i$。

考虑这么转化过后会有什么好处，假设我们现在走到了点 $(u,x)$ ，通过一条长度为 $y$ 的边 $u \rightarrow v$ 我们可以走到 $(v, 2x + y)$，然后我们可以重新走回来，走到 $(u,4x+3y)$，再走到 $(v, 8x+7y)$ …也就是说，我们可以通过 $(v, 2x + y)$ 走到 $(u, 2^{2k}(x + y) - y)$ ，易证一定存在一个 $2^k\equiv 1\pmod{Mod}$ (必然存在 $2^a\equiv 2^b\pmod{Mod}$ 且 $a\neq b$，那么 $2^{|a-b|}就是一个$) ，所以我们可以从 $(v, 2x + y)$ 重新走回 $(u, x)$ ，这也就意味这我们通过拆点得到的新图上的每一条边都是双向的。

然后考虑另一件事，假设我们通过一条长度为 $w_1$ 的边从 $(u,x)$ 可以走到 $(u,4x+3w_1)$ ，通过另一条长度为 $w_2$ 的边可以走到 $(u, 4x + 3w_2)$ ，因为所有的边都是双向边，所以我们可以从$(u,4x+3w_1)$ 走到 $(u,4x + 3w_2)$ 。显然 4 在模奇素数的情况下存在逆元，所以 $4x$ 可以代表任何数，从而我们得到从 $(u,x)$ 可以走到 $(u, x + (3w_2 - 3w_1))$。

通过辗转相除法之类的理论，我们可以毛估估的得到，我们从 $(u,x)$ 可以走到 $(u,x + gcd(3g, Mod))$，其中 $g$ 为所有与 $u$ 相邻的边两两之差的 $gcd$ ，那么对于每个点，与 3g 同余的状态就都是等价的了。又因为我们可以从 $(u, x)$ 走到 $(v, 2x + y)$，他们两个点的循环节为 $3g_u,3g_v$ 那么对 $v$ 这个点，循环节的大小就可以缩小成 $gcd(3g_u,3g_b)$ 了。毛估估一下，对于每个点 $i$ ，都可以从 $(i, x)$ 走到 $(i + gcd(3t, Mod))$，其中 $t = gcd(3g_1, 3g_2\cdots3g_n)$，换句话说，t 就是整张图每条边两两差值的$gcd$。

那么对于每条边，一定都和 t 同余，我们不妨令这个余数为 $z$ ，这时我们让每个状态的第二维往上抬 $z$，同时令每一条边的边权 $-z$，每一条边的边权就变成了 t 的倍数，同时 $(u,x)$ 依旧可以到达 $(v, (2x - z) + (y + z)) = (v, 2x + y)$ 。因为循环节的大小一定是 $3t$ 的约数，所以我们只关心这个倍数模三是多少，于是现在状态已经缩小到 $(u, 2^kx + pt)$，其中 $0 \leq t < 3$ 。

下一步就是怎么把 $k$ 优化了，因为 $(u, x)$ 可以到达 $(u, 4x + 3y)$，同时 $3y \% 3t \equiv 0$ ，所以 $(u, x)$ 可以到达 $(u, 4x)$ ，也就是说，我们现在只关心 $k$ 的奇偶性了，剩下的都是互相可达的状态。

于是这张图的每个点只需要拆成6个点，我们对这个 $6n$ 个点的图跑个并查集就可以维护连通性了。现在再来看这个询问，就是求 $(s, z)$ 是否能到达 $(t, z + r)$ ，我们枚举一下 $p, q$ ，询问就变成了求 $2^{2k+p}z + qt = z+r$ 并且这两个点是否连通。前半部分相当于求 $2^{2k+p}z = z+r-qt$ 是否存在这样的 $k$ ，这玩意对于每个$[0, Mod)$ 与处理一下就好了，毛估估$O(Mod + nlogn)$

Code

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
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <map>
#include <set>
#include <ctime>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cctype>
#include <string>
#include <numeric>
#include <cstring>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std ;
#define int long long
#define rep(i, a, b) for (ll i = (a); i <= (b); ++i)
#define per(i, a, b) for (ll i = (a); i >= (b); --i)
#define loop(it, v) for (auto it = v.begin(); it != v.end(); it++)
#define cont(i, x) for (ll i = head[x]; i; i = edge[i].nex)
#define clr(a) memset(a, 0, sizeof(a))
#define ass(a, cnt) memset(a, cnt, sizeof(a))
#define cop(a, b) memcpy(a, b, sizeof(a))
#define lowbit(x) (x & -x)
#define all(x) x.begin(), x.end()
#define SC(t, x) static_cast <t> (x)
#define ub upper_bound
#define lb lower_bound
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define pof pop_front
#define pob pop_back
#define fi first
#define se second
#define y1 y1_
#define Pi acos(-1.0)
#define iv inline void
#define enter putchar('\n')
#define siz(x) ((ll)x.size())
#define file(x) freopen(x".in", "r", stdin),freopen(x".out", "w", stdout)
typedef double db ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair <ll, ll> pii ;
typedef vector <ll> vi ;
typedef vector <pii> vii ;
typedef queue <ll> qi ;
typedef queue <pii> qii ;
typedef set <ll> si ;
typedef map <ll, ll> mii ;
typedef map <string, ll> msi ;
const ll maxn = 2e6 + 100 ;
const ll inf = 0x3f3f3f3f ;
const ll iinf = 1 << 30 ;
const ll linf = 2e18 ;
// const ll mod = 998244353 ;
const double eps = 1e-7 ;
template <class T = ll> T chmin(T &a, T b) { return a = min(a, b);}
template <class T = ll> T chmax(T &a, T b) { return a = max(a, b);}
template <class T = ll> T read()
{
    T f = 1, a = 0;
    char ch = getchar() ;
    while (!isdigit(ch)) { if (ch == '-') f = -1 ; ch = getchar() ; }
    while (isdigit(ch)) { a =  (a << 3) + (a << 1) + ch - '0' ; ch = getchar() ; }
    return a * f ;
}

ll n, m, q, tmp_mod, t, z;

ll u[maxn], v[maxn], w[maxn];

ll fa[maxn];

ll gcd(ll a, ll b)
{
    return !b ? a : gcd(b, a % b);
}

ll getfa(ll a)
{
    return a == fa[a] ? a : fa[a] = getfa(fa[a]) ;
}

void init()
{
    rep(i, 1, 6 * n) fa[i] = i;
}

void merge(ll a, ll b)
{
    // printf("%lld -> %lld\n", a, b);
    if(a < 1 || a > 6 * n) return (void)(puts("NMSL"), exit(0));
    if(b < 1 || b > 6 * n) return (void)(puts("NMSL"), exit(0));
    a = getfa(a), b = getfa(b);
    if(a != b) fa[a] = b;
}

vi edge[maxn];

void add(ll u, ll v, ll w)
{
    merge(u, v + (3 + w) * n);
    merge(u + n, v + ((2 + w) % 3 + 3) * n);
    merge(u + 2 * n, v + ((4 + w) % 3 + 3) * n);
    merge(u + 3 * n, v + w * n);
    merge(u + 4 * n, v + ((2 + w) % 3) * n);
    merge(u + 5 * n, v + ((4 + w) % 3) * n);
}

ll vis[maxn][2], flag[maxn][2];

signed main()
{
    n = read(), m = read(), q = read(), tmp_mod = read();
    rep(i, 1, m) u[i] = read(), v[i] = read(), w[i] = read(), t = gcd(abs(w[i] - w[1]), t);
    init();
    if(!t) t = tmp_mod;
    z = w[1] % t;
    // printf("nmsl : %lld %lld\n", t, z);
    rep(i, 1, m)
    {
        w[i] = (w[i] - z) / t % 3;
        // printf("%lld\n", w[i]);
        // printf("%lld %lld\n", u[i], v[i]);
        add(u[i], v[i], w[i]), add(v[i], u[i], w[i]);
    }
    // return 0;
    ll c = gcd(3 * t, tmp_mod);
    // printf("%lld\n", c);
    ll tmp = 2;
    while(1)
    {
        if(vis[tmp][1]) break;
        vis[tmp][1] = 1, flag[tmp * z % c][1] = 1;
        // printf("%lld %lld\n", tmp * z % c, 1);
        (tmp *= 4) %= c;
    }
    tmp = 1;
    while(1)
    {
        if(vis[tmp][0]) break;
        vis[tmp][0] = 1, flag[tmp * z % c][0] = 1;
        // printf("%lld %lld\n", tmp * z % c, 0);
        (tmp *= 4) %= c;
    }
    // rep(i, 1, 6 * n) printf("%lld ", getfa(i));
    // puts("");
    // printf("%lld\n", t);
    while(q --)
    {
        ll u = read(), v = read(), r = read();
        swap(u, v);
        ll ans = 0;
        rep(i, 0, 1) rep(j, 0, 2)
        {
            // printf("%lld %lld : \n", i, j);
            // printf("%lld %lld\n", getfa(u) == getfa(v + (i * 3 + j) * n), (z + r + c - j * t % c) % c);
            if(getfa(u) == getfa(v + (i * 3 + j) * n) && flag[(z + r + c - j * t % c) % c][i]) ans = 1;
        }
        puts(ans ? "YES" : "NO");
    }
    return 0;
}
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2020-2022 naitir
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信