kmjp's blog

競技プログラミング参加記です

AtCoder ABC #294 : Ex - K-Coloring

ARC

また知らないテクニックが出てきた…。
https://atcoder.jp/contests/abc294/tasks/abc294_h

問題

N頂点M辺の無向グラフが与えられる。
各点をK色のいずれかで塗り分けるとき、辺の端点の2頂点は異なる色となるようにしたい。
塗り分け方は何通りか。

解法

まず辺の次数が小さい点を削除していく。

  • 次数0の点はK色のいずれでも良い。
  • 次数1の点は隣接点と異なる(K-1)色のいずれでも良い。
  • 次数2の点は、包除原理の要領で、その点が隣接する2点と同じ色になるケースを考えて足し引きすればよい。

残すケースは、各点が次数3以上の場合であり、この際頂点数はM*2/3=20以下である。
あとはN=20以下の場合の彩色を考える。
同じ色を取ってよい点の組み合わせをK個集めて、N頂点を構成することを考える。
これはO(N*3^N)で解けるがN=20だと間に合わない。そこでO(N^2*2^N)に落とし込む必要がある。

これはEditorialにある通り2^N個のN次式をたたみこんだ上で多項式をK乗し、畳み込みをもとに戻すことで求められる。

int N,M,K;
vector<pair<int,int>> E;
const ll mo=998244353;

vector<pair<int,int>> goswap(vector<pair<int,int>> E,int a,int b) {
	FORR2(x,y,E) {
		if(x==a) x=b;
		else if(x==b) x=a;
		if(y==a) y=b;
		else if(y==b) y=a;
		
	}
	return E;
}


vector<ll> FPS_pow(vector<ll> F,int K) {
	const int NUM_=40001;
	static ll inv[NUM_+1];
	if(inv[1]==0) {
		inv[1]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	}

	int N=F.size();
	vector<ll> G(N);
	assert(F[0]==1);
	G[0]=1;
	int i,j;
	for(i=1;i<N;i++) {
		ll co=K+1-i;
		for(j=1;j<=i;j++) {
			(G[i]+=F[j]*G[i-j]%mo*co)%=mo;
			co=(co+K+1)%mo;
		}
		G[i]=G[i]*inv[i]%mo;
	}
	
	return G;
}

ll subset(int N,vector<ll> F) {
	int M=1<<N;
	vector<vector<ll>> G;
	G.resize(M);
	FORR(g,G) g.resize(N+1);
	int mask;
	FOR(mask,M) G[mask][__builtin_popcount(mask)]=F[mask];
	int i,j,x,y;
	//畳み込み
	FOR(i,N) {
		int len=1<<i;
		for(x=0;x<M;x+=2*len) {
			FOR(j,len) {
				FOR(y,N+1) {
					G[x+j+len][y]=(G[x+j+len][y]+G[x+j][y])%mo;
				}
			}
		}
	}
	FOR(mask,M) {
		G[mask]=FPS_pow(G[mask],K);
	}
	
	//戻す
	FOR(i,N) {
		int len=1<<i;
		for(x=0;x<M;x+=2*len) {
			FOR(j,len) {
				FOR(y,N+1) {
					G[x+j+len][y]=(G[x+j+len][y]-G[x+j][y]+mo)%mo;
				}
			}
		}
	}
	return G.back()[N];
}

ll go(int N,vector<pair<int,int>> E) {
	vector<ll> F(1<<N);
	int mask;
	FOR(mask,1<<N) {
		int x,y;
		F[mask]=1;
		FORR2(a,b,E) {
			if((mask&(1<<a))&&(mask&(1<<b))) F[mask]=0;
		}
	}
	return subset(N,F);
}

ll dfs(int N,vector<pair<int,int>> E) {
	
	FORR2(a,b,E) if(a==b) return 0;
	if(N==0) return 1;
	vector<pair<int,int>> E2;
	FORR2(a,b,E) {
		if(a>b) swap(a,b);
		if(b<N) E2.push_back({a,b});
	}
	sort(ALL(E2));
	E2.erase(unique(ALL(E2)),E2.end());
	E=E2;
	
	int C[30]={};
	FORR2(a,b,E) if(a<N&&b<N) C[a]++, C[b]++;
	int ma=0;
	int i;
	FOR(i,N) if(C[i]<C[ma]) ma=i;
	
	E=goswap(E,ma,N-1);
	if(C[ma]==0||C[ma]==1) {
		
		vector<pair<int,int>> E2;
		FORR2(a,b,E) {
			if(a>=N-1||b>=N-1) continue;
			E2.push_back({a,b});
		}
		return (K-C[ma])*dfs(N-1,E2)%mo;
	}
	else if(C[ma]==2) {
		
		vector<int> T;
		FORR2(a,b,E) {
			if(a==N-1&&b<a) T.push_back(b);
			if(b==N-1&&a<b) T.push_back(a);
		}
		
		int x=T[0],y=T[1];
		ll ret=(K-2+mo)*dfs(N-1,E)%mo;
		vector<pair<int,int>> E2;
		if(x==N-2) {
			swap(x,y);
		}
		else {
			E=goswap(E,y,N-2);
		}
		y=N-2;
		FORR2(a,b,E) {
			if(a>=N-1||b>=N-1) continue;
			if(a==y) E2.push_back({x,b});
			else if(b==y) E2.push_back({a,x});
			else E2.push_back({a,b});
		}
		return (ret+dfs(N-2,E2))%mo;
	}
	else {
		return go(N,E);
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>K;
	FOR(i,M) {
		cin>>x>>y;
		E.push_back({x-1,y-1});
	}
	cout<<dfs(N,E)<<endl;
}

まとめ

ABCのEx、毎回数え上げ系が極端に難しい印象があるな…。