寻求纯净之瞳欲往虹之彼侧

FutaRimeWoawaSete · 2023-03-17 22:05:27 · 题解

P6914

从 ix35 论文来的！

深受震撼！！！！！！

我们考虑一个很奇怪的想法：如果你看过 ix35 的论文，你就会知道所有简单环都可以由环空间的一个基进行线性组合得来。

其中一个基的构造是，找到每个联通分量的 dfs 树，然后只找每条返祖边和树上路径组成的环构成一组基，所有的简单环都可以由这些基进行线性组合得到。

我们考虑切边等价。大胆猜结论：按照切边等价划分等价类，设第 i 个等价类是 U_i，那么答案就是 \gcd(|U_i|)。

切边等价指的是，两条边 e_1,e_2 等价当且仅当它们被覆盖的简单环集合相同。

ix35 之后使用了 FWT 进行说明，但是我们有一个更直观的理解思路：

在此之前，我们还是要阐明一个大多数题解证明的结论，即假设两个相交的环 A,B，我们拆成三部分 S_1,S_2,S_3 分别表示 A 对应在对称差的部分，B 对应在对称差的部分和两个环的交，注意都是边集。可以发现 S_1,S_2,S_3 必须平均划分颜色，否则经过讨论会不合法（这个感觉还是比较简单的，如果你真的没看懂看看其它题解的说法会清楚很多，过于平凡就不讲了）；
有了这个结论，我们就可以说明我们所需求的就是这些 \gcd(|S_1|,|S_2|,|S_3|) 的 \gcd，我们可以证明的是我们只需要求出所有的切边等价类的 \gcd 就行了。
显然每个切边等价类会被纳入 \gcd 的贡献，即它们肯定是某两个环的交（否则切边等价类肯定会拓展，并且它们也不会细分了，否则就不是切边等价类了）
而其中的 S_1,S_2 如果不是同一个切边等价类，那么它们肯定可以细分成许多个切边等价类拼在一起，根据更相减损法，最后要被纳入贡献的 |S_1| 一定会被细分的若干个切边等价类 U_1,U_2,U_3,\dots U_k，在计算 \gcd(|U_1|,|U_2|,|U_3|,\dots |U_k|) 时就已经被计算贡献了。

也许不太严谨？可能反倒是一种理解，如果你会直接数学证明是再好不过的！！！

然后就是怎么求所有切边等价类。一个确定性算法是，你发现根据切边等价的定义，同一切边等价类的边被覆盖的简单环集合相同，删去其中一条边，切边等价类剩余的边肯定都没有简单环覆盖，那么它就是割边，直接再跑 tarjan 就可以维护了。

我是一条笨笨军犬怎么办？ix35 的论文中提到一个想法：我们实际维护的时候只需要维护每条边被基中的环（树路径加一条非树边组成的环）的覆盖情况，相同就切边等价（其它环由基中的环线性组合得到），那么我们直接上 hash，先随便找棵 dfs 树，找到返祖边就随机一个权值上去，然后对于路径上的边打按位异或的树上差分标记，最后值相同的个就可以默认是切边等价的。

瓶颈在排序，你喜欢可以写 O(n)，code O(n \log n)。

也就比 O(n ^ 2) 快一点。无语了。

#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define int ll
const int Len = 3005 + 5;
mt19937 rnd(time(0));
uniform_int_distribution<ll> op1(0 , (1ll << 62));
int n,m,head[Len],cnt,dfn[Len],low[Len],tim,ist[Len],vis[Len],dep[Len],fa[Len];
ll bot[Len],tbot[Len],cc[Len];int len,idd[Len];
struct node
{
    int next,to,ID;
}edge[Len << 1];
inline void add(int from,int to,int id)
{
    edge[++ cnt].to = to;
    edge[cnt].ID = id;
    edge[cnt].next = head[from];
    head[from] = cnt;
}
void tarjan(int u,int fa)
{
    dfn[u] = low[u] = ++ tim;
    for(int e = head[u] ; e ; e = edge[e].next)
    {
        int to = edge[e].to;
        if(!dfn[to])
        {
            tarjan(to , u);
            low[u] = min(low[u] , low[to]);
            if(low[to] > dfn[u])
            {
                ist[edge[e].ID] = 1;
            }
        }
        else if(to != fa)
            low[u] = min(low[u] , dfn[to]);
    }
}
int ve[Len];
void dfs(int u,int f)
{
    //printf("###%d\n",u);
    dep[u] = dep[f] + 1;
    vis[u] = 1;
    fa[u] = f;
    for(int e = head[u] ; e ; e = edge[e].next)
    {
        int to = edge[e].to;
        //printf("eee%d\n",edge[e].ID);
        if(to == f) continue;
        if(vis[to])
        {       
            if(dep[to] < dep[u] && dep[to] != dep[u] - 1)
            {
                ve[edge[e].ID] = 1;//printf("!!!%d\n",edge[e].ID);
                tbot[edge[e].ID] = op1(rnd);
                bot[u] ^= tbot[edge[e].ID] , bot[to] ^= tbot[edge[e].ID];
            }
        }
        else
        {
            idd[to] = edge[e].ID;
            ve[edge[e].ID] = 1;
            //printf("!!!%d\n",edge[e].ID);
            dfs(to , u);
        }
    }
}
void DFS(int u,int f)
{
    vis[u] = 1;
    for(int e = head[u] ; e ; e = edge[e].next)
    {
        int to = edge[e].to;
        if(to == f) continue;
        if(dep[to] != dep[u] + 1) continue;
        DFS(to , u);
        bot[u] ^= bot[to];
    }
    //printf("%d %lld\n",u,bot[u]);
}
inline ll gcd(ll a,ll b)
{
    if(!b) return a;
    return gcd(b , a % b);
}
signed main()
{
    scanf("%lld %lld",&n,&m);
    for(int i = 1 ; i <= m ; i ++)
    {
        int x,y;scanf("%lld %lld",&x,&y);
        add(x , y , i) , add(y , x , i);
    }
    for(int i = 1 ; i <= n ; i ++) if(!dfn[i]) tarjan(i , 0);
    memset(vis , 0 , sizeof vis);
    for(int i = 1 ; i <= n ; i ++) if(!vis[i]) dfs(i , 0);
    memset(vis , 0 , sizeof vis);
    for(int i = 1 ; i <= n ; i ++) if(!vis[i]) DFS(i , 0);
    //for(int i = 1 ; i <= m ; i ++) if(!ve[i]) printf("xxx%d\n",i);
    for(int i = 2 ; i <= n ; i ++) 
    {
        if(ist[idd[i]]) continue;
        tbot[idd[i]] = bot[i];
    }
    for(int i = 1 ; i <= m ; i ++) 
    {
        if(ist[i]) continue;
        cc[++ len] = tbot[i];
    }
    sort(cc + 1 , cc + 1 + len);
    //printf("%d\n",len);
    //for(int i = 1 ; i <= len ; i ++) printf("%d %lld\n",i,cc[i]);
    ll GCD = 0;
    for(int l = 1 , r = 0 ; l <= len ; l = r + 1)
    {
        r = l;
        while(r + 1 <= len && cc[r + 1] == cc[l]) r ++;
        GCD = gcd(GCD , r - l + 1);
    }
    vector<int> Pt;
    for(int i = 2 ; i * i <= GCD ; i ++) 
    {
        if(GCD % i == 0) 
        {
            Pt.push_back(GCD / i);
            if(i * i != GCD) Pt.push_back(i);
        }
    }
    Pt.push_back(1);if(GCD != 1) Pt.push_back(GCD);
    sort(Pt.begin() , Pt.end());const int SZ = (int)Pt.size();for(int j = 0 ; j < SZ ; j ++) printf("%lld ",Pt[j]);
    return 0;
}

寻求纯净之瞳 欲往 虹之彼侧

寻求纯净之瞳欲往虹之彼侧