题解：P14310 【MX-S8-T3】图排列

· · 题解

何意味？

Solution

注意到长度为 5 的所有置换构成的群的不同子群仅有 156 种。

枚举一个子群 G，对于所有满足 w\in G 的边 (u,v,w) 在 u,v 间连一条边，连完边后若 x,y 连通就说明存在一条 x 到 y 的路径的生成子群是 G 的子群。求出所有满足 x,y 连通的所有 \min |G| 即可。

Code

bool Mst;
#include<bits/stdc++.h>
using namespace std;
using ui=unsigned int;
using ll=long long;
using ull=unsigned long long;
using i128=__int128;
using u128=__uint128_t;
using pii=pair<int,int>;
#define fi first
#define se second
constexpr int N=2e5+5,mod=998244353,INF=1e9;
constexpr i128 one=1;
inline ll add(ll x,ll y){return (x+=y)>=mod&&(x-=mod),x;}
inline ll Add(ll &x,ll y){return x=add(x,y);}
inline ll sub(ll x,ll y){return (x-=y)<0&&(x+=mod),x;}
inline ll Sub(ll &x,ll y){return x=sub(x,y);}
inline ll qpow(ll a,ll b){
    ll res=1;
    for(;b;b>>=1,a=a*a%mod)
        if(b&1)res=res*a%mod;
    return res;
}
namespace Size5PermGroup{
    vector<vector<int> > perm;
    map<vector<int>,int> id;
    int prod[120][120];
    inline vector<int> operator *(const vector<int> &p,const vector<int> &q){
        assert(p.size()==q.size());
        vector<int> r(p.size());
        for(int i=0;i<(int)r.size();i++)r[i]=p[q[i]];
        return r;
    }
    inline int lg(i128 x){return x>>64?__lg((ull)(x>>64))+64:__lg((ull)x);}
    inline int popc(i128 x){return __builtin_popcountll((ull)(x>>64))+__builtin_popcountll((ull)(x&-1ull));}
    struct cmp{
        inline bool operator ()(i128 u,i128 v)const{
            return popc(u)>popc(v);
        }
    };
    priority_queue<i128,vector<i128>,cmp> q;
    map<i128,bool> vis;map<i128,int> Id;
    inline i128 ext(i128 x){
        i128 vis=0;
        while(vis!=x){
            int i=lg(vis^x);
            vis|=one<<i;
            for(int j=0;j<120;j++)
                if(x>>j&1)
                    x|=one<<prod[i][j];
        }
        return x;
    }
    i128 st[156];int siz[156],to[156][120];
    inline void init(){
        vector<int> vec(5);
        for(int i=0;i<5;i++)vec[i]=i;
        do id[vec]=perm.size(),perm.emplace_back(vec);
        while(next_permutation(vec.begin(),vec.end()));
        for(int i=0;i<120;i++)
            for(int j=0;j<120;j++)
                prod[i][j]=id[perm[i]*perm[j]];
        int cnt=0;
        q.emplace(1),vis[1]=1;
        while(q.size()){
            i128 x=q.top();q.pop();
            int o=cnt++;
            Id[st[o]=x]=o,siz[o]=popc(x);
            for(int i=0;i<120;i++)
                if(!(x>>i&1)){
                    i128 y=ext(x|one<<i);
                    if(!vis[y])
                        q.emplace(y),vis[y]=1;
                }
        }
        for(int i=0;i<156;i++)
            for(int j=0;j<120;j++)
                to[i][j]=Id[ext(st[i]|one<<j)];
    }
}
using Size5PermGroup::id;
using Size5PermGroup::to;
using Size5PermGroup::siz;
int n,m,q;
struct node{
    int u,v,w;
    node(){u=v=w=0;}
    node(int _u,int _v,int _w){u=_u,v=_v,w=_w;}
};
node e[N];pii qry[N];
int f[N],s[N];
inline int get(int x){return f[x]==x?x:f[x]=get(f[x]);}
inline void merge(int x,int y){
    x=get(x),y=get(y);
    if(x==y)return;
    if(s[x]>s[y])swap(x,y);
    f[x]=y,s[y]+=s[x];
}
int ans[N];
bool Med;
int main(){
    cerr<<abs(&Mst-&Med)/1048576.0<<endl;
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    Size5PermGroup::init();
    cin>>n>>m>>q;
    vector<int> vec(5);
    for(int i=0;i<m;i++){
        int u,v;cin>>u>>v,u--,v--;
        for(int j=0;j<5;j++)cin>>vec[j],vec[j]--;
        int w=id[vec];
        e[i]=node(u,v,w);
    }
    for(int i=0;i<q;i++)
        cin>>qry[i].fi>>qry[i].se,--qry[i].fi,--qry[i].se;
    for(int o=0;o<156;o++){
        for(int i=0;i<n;i++)f[i]=i,s[i]=1;
        for(int i=0;i<m;i++)
            if(to[o][e[i].w]==o)
                merge(e[i].u,e[i].v);
        for(int i=0;i<q;i++)
            if(!ans[i]&&get(qry[i].fi)==get(qry[i].se))
                ans[i]=siz[o];
    }
    for(int i=0;i<q;i++)
        if(ans[i])cout<<ans[i]<<'\n';
        else cout<<"No\n";
    return 0;
}