首页
A
yunf3grl
当前主题：自动模式
查看保存队列
搜索
专栏文章
2025.9.17 图的连通性问题
j
jjy412467
作弊者
2025/09/17 17:14
个人记录
参与者 1
已保存评论 0
文章操作
快速查看文章及其快照的属性，并进行相关操作。
当前评论
0 条
当前快照
1 份
快照标识符
@minvj4or
此快照首次捕获于
2025/12/02 09:02
3 个月前
此快照最后确认于
2025/12/02 09:02
3 个月前
查看原文
时光机
更新文章
复制链接
复制快照链接
复制正文 Markdown
CF1515G
“回到出发点”明示对连通分量独立考虑
一个观察是一个环走
k
k
k
次相当于没走
t
×
r
i
n
g
i
≡
0
(
m
o
d
t
)
t \times ring_i \equiv 0 \pmod t
t
×
r
in
g
i
≡
0
(
mod
t
)
那门在一个连通分量里我们就可以对于一个序列
k
i
k_i
k
i
构造一个方案使得
r
i
n
g
i
ring_i
r
in
g
i
记入
k
i
k_i
k
i
次
我们就要构造方案
s
+
∑
k
i
×
r
i
n
g
i
≡
0
(
m
o
d
t
)
s + \sum k_i \times ring_i \equiv 0 \pmod t
s
+
∑
k
i
×
r
in
g
i
≡
0
(
mod
t
)
感性地使用一下裴蜀定理
记
g
=
∑
k
i
×
r
i
n
g
i
g = \sum k_i \times ring_i
g
=
∑
k
i
×
r
in
g
i
一组
r
i
n
g
i
ring_i
r
in
g
i
可以表示出来的
g
g
g
为
g
c
d
(
r
i
n
g
i
)
gcd(ring_i)
g
c
d
(
r
in
g
i
)
的倍数
s
+
g
x
+
t
y
=
0
s + gx + ty = 0
s
+
gx
+
t
y
=
0
，当且仅当
g
c
d
(
t
,
g
)
∣
s
gcd(t,g) | s
g
c
d
(
t
,
g
)
∣
s
时有解
怎么
c
a
l
a
cala
c
a
l
a
出
g
g
g
显然求出所有一元环的
g
c
d
gcd
g
c
d
即可
这种东西可以
d
f
s
dfs
df
s
出它的生成树
返祖边是显然的
对于横插边，可以用
g
c
d
gcd
g
c
d
辗转相减的方法分析出贡献为
g
i
=
g
c
d
(
g
i
,
d
u
+
w
u
,
v
−
d
v
)
g_i = gcd(g_i,d_u+w_{u,v}-d_v)
g
i
=
g
c
d
(
g
i
,
d
u
+
w
u
,
v
−
d
v
)
相关推荐
评论
共 0 条评论，欢迎与作者交流。
最新优先
最早优先
搜索
正在加载评论...