P4796 题解

activeO · 2022-01-03 16:00:33 · 题解

题目大意

本题题面 讲的比较清楚了，这里不细说。

思路

考虑状压 dp， dp_{i,S} 表示走到 i 点，已用颜色的状态是 S 的方案数。

初始化：很显然 dp_{i,1<<(a_i-1)} 应该初始化为 1。

转移：先枚举状态，再枚举点进行转移，如果有两个点以上（即 S 中有 2 个 1 以上）就可以统计进答案。

易得转移方程： dp_{v,t|(1<<(a_v)-1)} \gets dp_{v,t|(1<<(a_v)-1)} + dp_{j,t}

代码

#include <bits/stdc++.h>//祝大家学习愉快！

#define int long long

using namespace std;

const int maxn=3e5+10;
struct edge{
    int to,nxt;
}e[maxn<<1];
int head[maxn],n,m,k,s;
int dp[maxn][40],a[maxn];
int dt[maxn],cnt=0,ans=0;

void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}

int lowbit(int x){
    return x&(-x);
}
int num1(int x){
    int res=0;
    while(x){
        res++;
        x-=lowbit(x);
    }
    return res;
}

bool cmp(int x,int y){
    return num1(x)<num1(y);
}

inline void init(){
    s=(1<<k)-1;
    for(int i=1;i<=s;i++) dt[i]=i;
    sort(dt+1,dt+s+1,cmp);
    memset(dp,0,sizeof(dp));
    memset(head,-1,sizeof(head));
}
void solve(){
    for(int i=1;i<=n;i++) dp[i][1<<(a[i]-1)]=1;
    for(int i=1;i<=s;i++){
        int tmp=dt[i];
        for(int j=1;j<=n;j++){
            if(dp[j][tmp]){
                if(num1(tmp)>=2) ans+=dp[j][tmp];
                for(int k=head[j];k!=-1;k=e[k].nxt){
                    int v=e[k].to;
                    if(tmp&(1<<(a[v]-1))) continue;
                    dp[v][tmp|(1<<(a[v]-1))]+=dp[j][tmp];
                }
            }
        }
    }
}

signed main(){

    scanf("%lld %lld %lld",&n,&m,&k);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);

    init();

    for(int i=1;i<=m;i++){
        int u,v;
        scanf("%lld %lld",&u,&v);
        add(u,v);
        add(v,u);
    }

    solve();

    printf("%lld\n",ans);

    return 0;
}