P8315 [COCI2021-2022#4] Šarenlist

orange_dream · 2023-10-09 19:27:40 · 题解

考虑使用容斥，考虑每条路径满足或不满足的方案。

答案为 \sum -1^{popcount(i)}f(i)。

发现不合法的颜色必须一样，所以使用并查集来维护，将每个不合法用一个虚拟点来表示，设最终并查集中根节点的个数为 num，则答案为 k^{num}，即 f(i)=k^{num}。

献上赛后改对的代码一枚。

#include<bits/stdc++.h>

#define int long long

using namespace std;

const int N=1e6,mod=1e9+7;
int n,m,color,a,b,c[N],d[N],fa[N],ans,f[N],dd[N],xx[N],yy[N];
bool st[N];
vector<int> G[N];
queue<int> q;

void read(int &x){
    char c=getchar();int F=1;x=0;
    while (!isdigit(c) && c!='-')c=getchar();
    if (c=='-')F=-1,c=getchar();
    while (isdigit(c))x=x*10+c-48,c=getchar();
}
void write(int x){if (x>9)write(x/10);putchar(x%10+'0');}

int find(int x){if (f[x]==x)return x;return f[x]=find(f[x]);}//并查集
void merge(int x,int y){x=find(x);y=find(y);if (x!=y)f[x]=y;}

void bfs(int x){
    q.push(x);
    st[x]=true;
    while (!q.empty()){
        int x=q.front();
        q.pop();
        for (int i=0;i<G[x].size();i++){
            int v=G[x][i];
            if (st[v])continue;
            st[v]=true;
            q.push(v);
            d[v]=d[x]+1;
            fa[v]=x;
        }
    }
}

int qmi(int x,int y){
    int ans=1;
    while (y){
        if (y&1)ans=ans*x%mod;
        y>>=1;
        x=x*x%mod;
    }
    return ans;
}

int lca(int x,int y,int ou){
    if (x==y)return x;
    if (d[x]<d[y])swap(x,y);
    while (d[x]>d[y]){
        merge(x,ou);//x表示x->fa[x]这条边
        x=fa[x];
    }
    if (x==y)return x;
    while (x!=y){
        merge(x,ou);merge(y,ou);
        x=fa[x];y=fa[y];
    }
    return x;
}

signed main(){
    read(n);read(m);read(color);
    for (int i=1;i<n;i++){
        read(a);read(b);
        G[a].push_back(b);
        G[b].push_back(a);
    }
    bfs(1);
    for (int i=1;i<=m;i++){
        read(c[i]);read(dd[i]);
    }
    int ans,sum=0,flag,gg,len;
    for (int i=0;i<(1<<m);i++){//O(2^m*n*m*log(n))
        len=n;
        flag=1;
        ans=1;
        for (int j=1;j<=m+n;j++)f[j]=j;
        for (int j=0;j<m;j++){
            if (i&(1<<j)){
                flag*=-1;
                gg=lca(c[j+1],dd[j+1],++len);
            }
        }
        for (int j=1;j<=len;j++){
            if (j==find(j))ans*=color,ans%=mod;
        }
        ans=ans*qmi(color,mod-2)%mod;
        sum+=ans*flag;
        sum%=mod;
    }
    printf("%lld\n",(sum+mod)%mod);
    return 0;
}

第一篇题解，求过。