自动搬运

查看原文

来自洛谷，原作者为

	activeO **

搬运于2025-08-24 22:03:42，当前版本为作者最后更新于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;
}