自动搬运

查看原文

来自洛谷，原作者为

	liuzhangfeiabc **

搬运于2025-08-24 22:09:57，当前版本为作者最后更新于2019-05-09 21:02:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意：2×n的格子，用c种颜色进行染色，要求相邻的格子不能用相同的颜色，一些格子已经事先涂好了颜色，求方案数。

先%一下现场切掉这题的rqy。

我这里的做法与rqy的不同，我没看过官方题解不过我猜这个做法应该类似于官方题解的思路。

先考虑一个最朴素的dp。设f(i,j,k)为前i列，最后一列上面填j下面填k的方案数，转移直接枚举下一列填什么。

这样做显然复杂度非常高，光状态数就达到了nc^2。

我们该怎么优化这个算法呢？

首先当然是要把状态数减下来。我们把视线放在这个c^2上，能否在这里做些手脚呢？

注意到当这一列已经有事先填过的格子时，我们显然只需要c的状态就可以了。

假设当前列的上面已经填了颜色x，我们就直接记f(y)表示下面格子填y的方案数，其中f(x)=0。下面填了颜色类似。为方便起见，我们可以将上下都填颜色当成上面填颜色处理。

那我们处理到了没填过的列该怎么办呢？注意到所有没填过的列都长成一个样子，我们就自然而然地想到了：或许可以预处理转移！

我们直接将所有连续的空列看成一大段来一起转移，只在所有非空列更新dp值。

预处理一个数组g(i,s)，表示相邻两个非空列中间隔着i个空列，这两个非空列的状态为s时的转移系数。

其中这个“状态”指的是对应元素的相等关系。一共有如下7种状态：

a ... a
b ... b
*******
a ... b
b ... a
*******
a ... a
b ... c
*******
a ... b
b ... c
*******
a ... c
b ... a
*******
a ... c
b ... b
*******
a ... c
b ... d

其中状态3和6，状态4和5是对称的，因此我们记5种状态即可。

g数组的预处理就是大分类讨论，细节详见代码。这一步是O(n)的。

这样我们只需要枚举所有非空列，也可以通过讨论一些列的相等关系实现转移。

注意特判一些特殊情况，比如数据本来就无解、没有非空列、开头和结尾有一堆空列等。

这样我们就获得了一个O(nc)的做法，可以获得96分的好成绩。

更进一步：仔细观察dp的转移，发现我们无非干了这么几件事：

单点修改；全局加；全局乘；全局赋值；单点查询；全局查询。

嗯？好像有点熟悉？

没错你只需要把t1的代码粘过来就能获得100分的好成绩了。

当然你也可以直接上线段树，反正照样跑得飞快。

96分代码：

#include<bits/stdc++.h>
using namespace std;
#define gc getchar()
#define pc putchar
#define li long long
inline li read(){
	li x = 0,y = 0,c = gc;
	while(!isdigit(c)) y = c,c = gc;
	while(isdigit(c)) x = (x << 1) + (x << 3) + (c ^ '0'),c = gc;
	return y == '-' ? -x : x;
}
inline void print(li q){
	if(q < 0) pc('-'),q = -q;
	if(q >= 10) print(q / 10);
	pc(q % 10 + '0');
}
const li mo = 1000000009;
li n,c;
inline li ksm(li q,li w){
	li as = 1;
	while(w){
		if(w & 1) as = as * q % mo;
		q = q * q % mo;
		w >>= 1;
	}
	return as;
}
int a[100010],b[100010];
int wz[100010],ft;
li f[100010],g[100010][5],tp[100010];
int main(){
	int i,j,k,l,u,v,w;
	n = read();c = read();
	for(i = 1;i <= n;++i) a[i] = read();for(i = 1;i <= n;++i) b[i] = read();
	for(i = 1;i <= n;++i){
		if(a[i] || b[i]) wz[++ft] = i;
		if(a[i] && a[i] == b[i]){
			pc('0');pc('\n');return 0;
		}
		if(i < n && ((a[i] && a[i] == a[i + 1]) || (b[i] && b[i] == b[i + 1]))){
			pc('0');pc('\n');return 0;
		}
	}
	if(!ft){
		li as = c * (c - 1) % mo;
		for(i = 2;i <= n;++i) (as *= (c - 1 + (c - 2) * (c - 2) % mo) % mo) %= mo;
		print(as);pc('\n');return 0;
	}
	g[1][1] = g[1][3] = g[1][4] = 1;
	for(i = 2;i <= n;++i){
		g[i][0] = (g[i - 1][1] + g[i - 1][3] * (c - 2) * 2 + g[i - 1][4] * (c - 2) % mo * (c - 3)) % mo;
		g[i][1] = (g[i - 1][0] + g[i - 1][2] * (c - 2) * 2 + g[i - 1][4] * (c - 2) % mo * (c - 3)) % mo;
		g[i][2] = (g[i - 1][1] + g[i - 1][2] * (c - 2) + g[i - 1][3] * (c - 2 + c - 3) + g[i - 1][4] * (c - 3) % mo * (c - 3)) % mo;
		g[i][3] = (g[i - 1][0] + g[i - 1][3] * (c - 2) + g[i - 1][2] * (c - 2 + c - 3) + g[i - 1][4] * (c - 3) % mo * (c - 3)) % mo;
		g[i][4] = (g[i - 1][0] + g[i - 1][1] + g[i - 1][2] * (c - 3) * 2 + g[i - 1][3] * (c - 3) * 2 + g[i - 1][4] * (c - 3 + (c - 4) * (c - 4) % mo)) % mo;
	} 
	if(wz[1] == 1){
		if(a[1] && b[1]) f[b[1]] = 1;
		else if(a[1]){
			for(i = 1;i <= c;++i) if(i != a[1]) f[i] = 1;
		} 
		else{
			for(i = 1;i <= c;++i) if(i != b[1]) f[i] = 1;
		} 
	}
	else{
		int u = wz[1];
		if(a[u] && b[u]) f[b[u]] = (g[u - 1][0] + g[u - 1][1] + g[u - 1][2] * (c - 2) * 2 + g[u - 1][3] * (c - 2) * 2 + g[u - 1][4] * (c - 2) % mo * (c - 3)) % mo;
		else if(a[u]){
			for(i = 1;i <= c;++i) if(i != a[u]) f[i] = (g[u - 1][0] + g[u - 1][1] + g[u - 1][2] * (c - 2) * 2 + g[u - 1][3] * (c - 2) * 2 + g[u - 1][4] * (c - 2) % mo * (c - 3)) % mo;
		} 
		else{
			for(i = 1;i <= c;++i) if(i != b[u]) f[i] = (g[u - 1][0] + g[u - 1][1] + g[u - 1][2] * (c - 2) * 2 + g[u - 1][3] * (c - 2) * 2 + g[u - 1][4] * (c - 2) % mo * (c - 3)) % mo;
		} 
	}
	for(i = 2;i <= ft;++i){
		li s = 0;w = wz[i] - wz[i - 1];
		for(j = 1;j <= c;++j) s += f[j];s %= mo;
		if(a[wz[i]]){
			u = a[wz[i]];
			if(a[wz[i - 1]]){
				v = a[wz[i - 1]];
				for(j = 1;j <= c;++j) if(j != u && (!b[wz[i]] || j == b[wz[i]])){
					if(v == u) tp[j] = (f[j] * g[w][0] + (s - f[j] + mo) * g[w][2]) % mo;
					else if(v == j) tp[j] = (f[u] * g[w][1] + (s - f[u] + mo) * g[w][3]) % mo;
					else tp[j] = (f[u] * g[w][3] + f[j] * g[w][2] + (s - f[u] - f[j] + mo + mo) * g[w][4]) % mo;
				}
			}
			else{
				v = b[wz[i - 1]];
				for(j = 1;j <= c;++j) if(j != u && (!b[wz[i]] || j == b[wz[i]])){
					if(v == u) tp[j] = (f[j] * g[w][1] + (s - f[j] + mo) * g[w][3]) % mo;
					else if(v == j) tp[j] = (f[u] * g[w][0] + (s - f[u] + mo) * g[w][2]) % mo;
					else tp[j] = (f[u] * g[w][2] + f[j] * g[w][3] + (s - f[u] - f[j] + mo + mo) * g[w][4]) % mo;
				}
			}
		}
		else{
			u = b[wz[i]];
			if(a[wz[i - 1]]){
				v = a[wz[i - 1]];
				for(j = 1;j <= c;++j) if(j != u){
					if(v == u) tp[j] = (f[j] * g[w][1] + (s - f[j] + mo) * g[w][3]) % mo;
					else if(v == j) tp[j] = (f[u] * g[w][0] + (s - f[u] + mo) * g[w][2]) % mo;
					else tp[j] = (f[u] * g[w][2] + f[j] * g[w][3] + (s - f[u] - f[j] + mo + mo) * g[w][4]) % mo;
				}
			}
			else{
				v = b[wz[i - 1]];
				for(j = 1;j <= c;++j) if(j != u){
					if(v == u) tp[j] = (f[j] * g[w][0] + (s - f[j] + mo) * g[w][2]) % mo;
					else if(v == j) tp[j] = (f[u] * g[w][1] + (s - f[u] + mo) * g[w][3]) % mo;
					else tp[j] = (f[u] * g[w][3] + f[j] * g[w][2] + (s - f[u] - f[j] + mo + mo) * g[w][4]) % mo;
				}
			}
		}
		for(j = 1;j <= c;++j) f[j] = tp[j],tp[j] = 0;
	}
	li as = 0;
	if(wz[ft] == n) for(i = 1;i <= c;++i) (as += f[i]) %= mo;
	else{
		u = n - wz[ft];
		for(i = 1;i <= c;++i) (as += (g[u][0] + g[u][1] + g[u][2] * (c - 2) * 2 + g[u][3] * (c - 2) * 2 + g[u][4] * (c - 2) % mo * (c - 3)) % mo * f[i]) %= mo;
	}
	print((as % mo + mo) % mo);pc('\n');
	return 0;
}
/*
0:
aa
bb

1:
ab
ba

2:
aa or ac
bc    bb

3:
ab or ac
bc    ba

4:
ac
bd
*/

100分代码（线段树）：

#include<bits/stdc++.h>
using namespace std;
#define gc getchar()
#define pc putchar
#define li long long
inline li read(){
	li x = 0,y = 0,c = gc;
	while(!isdigit(c)) y = c,c = gc;
	while(isdigit(c)) x = (x << 1) + (x << 3) + (c ^ '0'),c = gc;
	return y == '-' ? -x : x;
}
inline void print(li q){
	if(q < 0) pc('-'),q = -q;
	if(q >= 10) print(q / 10);
	pc(q % 10 + '0');
}
const li mo = 1000000009;
li n,c;
int a[100010],b[100010];
int wz[100010],ft;
li f[100010],g[100010][5],tp[100010];
li t[400010],c1[400010],c2[400010],c3[400010];
#define ls q << 1
#define rs q << 1 | 1
#define ln ls,l,mid
#define rn rs,mid + 1,r
#define md int mid = l + r >> 1
inline void build(int q,int l,int r){
	c1[q] = -1;c2[q] = 1;c3[q] = 0;
	if(l == r){
		t[q] = f[l];return;
	}
	md;
	build(ln);build(rn);
	t[q] = (t[ls] + t[rs]) % mo;
}
inline void ud(li x,int op,int q,int l,int r){
	if(op == 1){
		c1[q] = x;c2[q] = 1;c3[q] = 0;t[q] = x * (r - l + 1) % mo;
	}
	else if(op == 2){
		(c2[q] *= x) %= mo;(c3[q] *= x) %= mo;(t[q] *= x) %= mo;
	}
	else{
		(c3[q] += x) %= mo;(t[q] += x * (r - l + 1)) %= mo;
	}
}
inline void ud(li x,int op){ud(x,op,1,1,c);}
inline void ps(int q,int l,int r){
	md;
	if(c1[q] != -1){
		ud(c1[q],1,ln);ud(c1[q],1,rn);c1[q] = -1;
	}
	if(c2[q] != 1){
		ud(c2[q],2,ln);ud(c2[q],2,rn);c2[q] = 1;
	}
	if(c3[q]){
		ud(c3[q],3,ln);ud(c3[q],3,rn);c3[q] = 0;
	}
}
inline void xg(int ax,li x,int op,int q,int l,int r){
	if(l == r){
		ud(x,op,q,l,r);return;
	}
	ps(q,l,r);md;
	if(mid >= ax) xg(ax,x,op,ln);
	else xg(ax,x,op,rn);
	t[q] = (t[ls] + t[rs]) % mo;
}
inline void xg(int ax,li x,int op){xg(ax,x,op,1,1,c);}
inline li cx(int x,int q,int l,int r){
	if(l == r) return t[q];
	ps(q,l,r);md;
	if(mid >= x) return cx(x,ln);
	return cx(x,rn);
}
inline li cx(int x){return cx(x,1,1,c);}
int main(){
	int i,j,u,v,w;
	li s,x,y;
	n = read();c = read();
	for(i = 1;i <= n;++i) a[i] = read();for(i = 1;i <= n;++i) b[i] = read();
	for(i = 1;i <= n;++i){
		if(a[i] || b[i]) wz[++ft] = i;
		if(a[i] && a[i] == b[i]){
			pc('0');pc('\n');return 0;
		}
		if(i < n && ((a[i] && a[i] == a[i + 1]) || (b[i] && b[i] == b[i + 1]))){
			pc('0');pc('\n');return 0;
		}
	}
	if(!ft){
		li as = c * (c - 1) % mo;
		for(i = 2;i <= n;++i) (as *= (c - 1 + (c - 2) * (c - 2) % mo) % mo) %= mo;
		print(as);pc('\n');return 0;
	}
	
	g[1][1] = g[1][3] = g[1][4] = 1;
	for(i = 2;i <= n;++i){
		g[i][0] = (g[i - 1][1] + g[i - 1][3] * (c - 2) * 2 + g[i - 1][4] * (c - 2) % mo * (c - 3)) % mo;
		g[i][1] = (g[i - 1][0] + g[i - 1][2] * (c - 2) * 2 + g[i - 1][4] * (c - 2) % mo * (c - 3)) % mo;
		g[i][2] = (g[i - 1][1] + g[i - 1][2] * (c - 2) + g[i - 1][3] * (c - 2 + c - 3) + g[i - 1][4] * (c - 3) % mo * (c - 3)) % mo;
		g[i][3] = (g[i - 1][0] + g[i - 1][3] * (c - 2) + g[i - 1][2] * (c - 2 + c - 3) + g[i - 1][4] * (c - 3) % mo * (c - 3)) % mo;
		g[i][4] = (g[i - 1][0] + g[i - 1][1] + g[i - 1][2] * (c - 3) * 2 + g[i - 1][3] * (c - 3) * 2 + g[i - 1][4] * (c - 3 + (c - 4) * (c - 4) % mo)) % mo;
	} 
	
	if(wz[1] == 1){
		if(a[1] && b[1]) f[b[1]] = 1;
		else if(a[1]){
			for(i = 1;i <= c;++i) if(i != a[1]) f[i] = 1;
		} 
		else{
			for(i = 1;i <= c;++i) if(i != b[1]) f[i] = 1;
		} 
	}
	else{
		int u = wz[1];
		if(a[u] && b[u]) f[b[u]] = (g[u - 1][0] + g[u - 1][1] + g[u - 1][2] * (c - 2) * 2 + g[u - 1][3] * (c - 2) * 2 + g[u - 1][4] * (c - 2) % mo * (c - 3)) % mo;
		else if(a[u]){
			for(i = 1;i <= c;++i) if(i != a[u]) f[i] = (g[u - 1][0] + g[u - 1][1] + g[u - 1][2] * (c - 2) * 2 + g[u - 1][3] * (c - 2) * 2 + g[u - 1][4] * (c - 2) % mo * (c - 3)) % mo;
		} 
		else{
			for(i = 1;i <= c;++i) if(i != b[u]) f[i] = (g[u - 1][0] + g[u - 1][1] + g[u - 1][2] * (c - 2) * 2 + g[u - 1][3] * (c - 2) * 2 + g[u - 1][4] * (c - 2) % mo * (c - 3)) % mo;
		} 
	}
	build(1,1,c);
	
	for(i = 2;i <= ft;++i){
		w = wz[i] - wz[i - 1];s = t[1];
		if(a[wz[i]] && b[wz[i]]){
			u = a[wz[i]];j = b[wz[i]];x = cx(u);y = cx(j);ud(0,1);
			if(a[wz[i - 1]]){
				v = a[wz[i - 1]];
				if(v == u) xg(j,(y * g[w][0] + (s - y + mo) * g[w][2]) % mo,1);
				else if(v == j) xg(j,(x * g[w][1] + (s - x + mo) * g[w][3]) % mo,1);
				else xg(j,(x * g[w][3] + y * g[w][2] + (s - x - y + mo + mo) * g[w][4]) % mo,1);
			}
			else{
				v = b[wz[i - 1]];
				if(v == u) xg(j,(y * g[w][1] + (s - y + mo) * g[w][3]) % mo,1);
				else if(v == j) xg(j,(x * g[w][0] + (s - x + mo) * g[w][2]) % mo,1);
				else xg(j,(x * g[w][2] + y * g[w][3] + (s - x - y + mo + mo) * g[w][4]) % mo,1);
			}
		}
		else if(a[wz[i]]){
			u = a[wz[i]];x = cx(u);
			if(a[wz[i - 1]]){
				v = a[wz[i - 1]];
				if(v == u){
					ud(g[w][0] - g[w][2] + mo,2);ud(s * g[w][2] % mo,3);
				}
				else{
					ud(g[w][2] - g[w][4] + mo,2);ud((x * g[w][3] + s * g[w][4] - x * g[w][4] % mo + mo) % mo,3);xg(v,(x * g[w][1] + (s - x + mo) * g[w][3]) % mo,1);
				}
			}
			else{
				v = b[wz[i - 1]];
				if(v == u){
					ud(g[w][1] - g[w][3] + mo,2);ud(s * g[w][3] % mo,3);
				}
				else{
					ud(g[w][3] - g[w][4] + mo,2);ud((x * g[w][2] + s * g[w][4] - x * g[w][4] % mo + mo) % mo,3);xg(v,(x * g[w][0] + (s - x + mo) * g[w][2]) % mo,1);
				}
			}
			xg(u,0,1);
		}
		else{
			u = b[wz[i]];x = cx(u);
			if(a[wz[i - 1]]){
				v = a[wz[i - 1]];
				if(v == u){
					ud(g[w][1] - g[w][3] + mo,2);ud(s * g[w][3] % mo,3);
				}
				else{
					ud(g[w][3] - g[w][4] + mo,2);ud((x * g[w][2] + s * g[w][4] - x * g[w][4] % mo + mo) % mo,3);xg(v,(x * g[w][0] + (s - x + mo) * g[w][2]) % mo,1);
				}
			}
			else{
				v = b[wz[i - 1]];
				if(v == u){
					ud(g[w][0] - g[w][2] + mo,2);ud(s * g[w][2] % mo,3);
				}
				else{
					ud(g[w][2] - g[w][4] + mo,2);ud((x * g[w][3] + s * g[w][4] - x * g[w][4] % mo + mo) % mo,3);xg(v,(x * g[w][1] + (s - x + mo) * g[w][3]) % mo,1);
				}
			}
			xg(u,0,1);
		}
	}
	
	for(i = 1;i <= c;++i) f[i] = cx(i);
	li as = 0;
	if(wz[ft] == n) for(i = 1;i <= c;++i) (as += f[i]) %= mo;
	else{
		u = n - wz[ft];
		for(i = 1;i <= c;++i) (as += (g[u][0] + g[u][1] + g[u][2] * (c - 2) * 2 + g[u][3] * (c - 2) * 2 + g[u][4] * (c - 2) % mo * (c - 3)) % mo * f[i]) %= mo;
	}
	print((as % mo + mo) % mo);pc('\n');
	return 0;
}