并不对劲的loj3111:p5359:[SDOI2019]染色

题目大意

有个2行n列的网格，c种颜色。
有些格子的颜色是固定的。
不能把相邻的格子染成同色，问剩下的格子的染色方案数模\(10^9+9\)。
\(n,c\leq 10^5;\)

题解

“相邻不同色”让人想到可以把染完色的段的两个右（左）端点染上的颜色记在状态里进行dp。
发现对于一段连续的没有颜色固定的格的列，它的染色方案只与它的长度和它前后两端的已染色的格的相同情况有关。
设\(f(i,S)\)表示一段长度为\(i\)的连续的没有颜色固定的格的、前后两端的已染色的格的相同情况为\(S\)的、列。
“前后两端的已染色的格的相同情况”有：有四种不同的颜色、有三种不同的颜色且颜色相同的格不同行、有三种不同的颜色且颜色相同的格同行、有两种不同的颜色且颜色相同的点同行、有两种不同的颜色且颜色相同的点不同行。
这样就可以设\(g(i,j)\)表示：考虑前\(i\)个含颜色固定的格的列，且最后一列不颜色固定的格的颜色为\(j\)。
观察\(g\)的转移，发现\(g(i-1,j)\)转移到\(g(i,j)\)相当于对\(g(i-1,j)\)进行了若干次单点修改、全局加、全局乘、全局修改、单点查询、全局和查询，这和“[SDOI2019]快速查询”这道题是一样的。

代码

#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define rep(i,x,y) for(register int i=(x);i<=(y);++i)
#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)
#define view(u,k) for(int k=fir[u];~k;k=nxt[k])
#define maxn 100007 
#define LL long long
using namespace std;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(!isdigit(ch)&&ch!=‘-‘)ch=getchar();
	if(ch==‘-‘)f=-1,ch=getchar();
	while(isdigit(ch))x=(x<<1)+(x<<3)+ch-‘0‘,ch=getchar();
	return x*f;
}
void write(int x)
{
	if(x==0){putchar(‘0‘),putchar(‘\n‘);return;}
	int f=0;char ch[20];
	if(x<0)putchar(‘-‘),x=-x;
	while(x)ch[++f]=x%10+‘0‘,x/=10;
	while(f)putchar(ch[f--]);
	putchar(‘\n‘);
	return;
}
const int mod=1e9+9;
int n,c,f[maxn][5],g[maxn],a[2][maxn],pos[maxn],cntp,tmp[2],inv2,admk,mulmk,lst[maxn],lstmk,tim;
int mo(int x){if(x<0)return x+mod;return x>=mod?x-mod:x;}
inline void upd(int & x,int y,int z){x=mo(x+(LL)y*z%mod);}
int mul(int x,int y){int res=1;while(y){if(y&1)res=(LL)res*x%mod;x=(LL)x*x%mod;y>>=1;}return res;}
int ask(int p,int id)
{
	if(id==1){return g[p];}
	else
	{
		if(lstmk>=lst[p])return admk;
		else return mo((LL)g[p]*mulmk%mod+admk);
	}
}
void chg(int p,int k){int tmp=ask(p,0);lst[p]=++tim;g[p]=(LL)mo(k-admk)*mul(mulmk,mod-2)%mod,g[0]=mo(g[0]+mo(k-tmp));return;}
void add(int k){admk=mo(admk+k),upd(g[0],k,c);return;}
void mult(int k)
{
	if(!k){lstmk=++tim,mulmk=1,admk=0,g[0]=0;return;}
	else mulmk=(LL)mulmk*k%mod,admk=(LL)admk*k%mod,g[0]=(LL)g[0]*k%mod;return;
}
int main()
{
	n=read(),c=read();inv2=mul(2,mod-2);
	rep(i,0,1)rep(j,1,n)a[i][j]=read();
	rep(i,1,n)if(a[0][i]&&a[1][i]&&a[0][i]==a[1][i]){write(0);return 0;}
	f[0][0]=f[0][4]=1,f[0][1]=2,f[0][2]=f[0][3]=0;
	int c33=(LL)(c-3)*(c-3)%mod,c23=(LL)(c-2)*(c-3)%mod,c22=(LL)(c-2)*(c-2)%mod;
	rep(i,1,n)
	{
		upd(f[i][0],f[i-1][0],mo(c33-(c-4)));
		upd(f[i][1],f[i-1][0],mo(2*mo(c23-(c-3))));
		upd(f[i][2],f[i-1][0],mo(2*mo(c23-(c-3))));
		upd(f[i][3],f[i-1][0],mo(c22-(c-2)));
		upd(f[i][4],f[i-1][0],mo(c22-(c-2)));
		upd(f[i][0],f[i-1][1],c-3);
		upd(f[i][1],f[i-1][1],c-2);
		upd(f[i][2],f[i-1][1],mo(c-2+c-3));
		upd(f[i][3],f[i-1][1],c-2);
		upd(f[i][0],f[i-1][2],c-3);
		upd(f[i][1],f[i-1][2],mo(c-2+c-3));
		upd(f[i][2],f[i-1][2],c-2);
		upd(f[i][4],f[i-1][2],c-2);
		upd(f[i][0],f[i-1][3],1);
		upd(f[i][1],f[i-1][3],2);
		upd(f[i][4],f[i-1][3],1);
		upd(f[i][0],f[i-1][4],1);
		upd(f[i][2],f[i-1][4],2);
		upd(f[i][3],f[i-1][4],1);
	}admk=0,mulmk=1;
	rep(i,1,n)if(a[0][i]|a[1][i])
	{
		pos[++cntp]=i;
		int fh=a[0][i]?0:1;
		if(cntp==1)
		{
			if(i==1)
			{
				rep(xc,1,c)
				{
					if(a[0][i]&&a[1][i]&&xc!=a[1][i])continue;
					if(xc!=a[fh][i])lst[xc]=++tim,g[xc]=1,upd(g[0],g[xc],1);
				}
			}
			else 
			{
				int sum=mo(mo(mo((LL)(c-2)*(c-3)%mod*f[i-2][0]%mod+(LL)(c-2)*f[i-2][1]%mod)+(LL)(c-2)*f[i-2][2]%mod)+mo(f[i-2][3]+f[i-2][4]));
				rep(xc,1,c)
				{
					if(a[0][i]&&a[1][i]&&xc!=a[1][i])continue;
					if(xc!=a[fh][i])lst[xc]=++tim,g[xc]=sum,upd(g[0],g[xc],1);
				}
			}
		}
		else
		{
			int fh2=a[0][pos[cntp-1]]?0:1,tmp=ask(a[fh][i],cntp-1),nowsum=g[0],len=i-pos[cntp-1]-1;
			if(a[0][i]&&a[1][i])
			{
				int tmp2=ask(a[1][i],cntp-1);mult(0);
				if(a[0][i]==a[fh2][pos[cntp-1]])chg(a[1][i],mo((LL)tmp2*f[len][fh==fh2?3:4]%mod+(LL)mo(nowsum-tmp2)*f[len][fh==fh2?2:1]%mod*inv2%mod));
				else if(a[1][i]==a[fh2][pos[cntp-1]])chg(a[1][i],mo((LL)tmp*f[len][fh==fh2?4:3]%mod+(LL)mo(nowsum-tmp)*f[len][fh==fh2?1:2]%mod*inv2%mod));
				else chg(a[1][i],mo((LL)mo(nowsum-tmp-tmp2)*f[len][0]%mod+mo((LL)tmp*f[len][fh==fh2?1:2]%mod*inv2%mod+(LL)tmp2*f[len][fh==fh2?2:1]%mod*inv2%mod)));
			}
			else if(a[fh2][pos[cntp-1]]==a[fh][i])
			{
				mult(mo(f[len][fh==fh2?3:4]-(LL)f[len][fh==fh2?2:1]*inv2%mod)),add((LL)nowsum*f[len][fh==fh2?2:1]%mod*inv2%mod),chg(a[fh][i],0);
			}
			else
			{
				mult(mo((LL)f[len][fh==fh2?2:1]*inv2%mod-f[len][0])),add(mo((LL)mo(nowsum-tmp)*f[len][0]%mod+(LL)tmp*f[len][fh==fh2?1:2]%mod*inv2%mod)),
				chg(a[fh2][pos[cntp-1]],mo((LL)mo(nowsum-tmp)*f[len][fh==fh2?1:2]%mod*inv2%mod+(LL)tmp*f[len][fh==fh2?4:3]%mod)),chg(a[fh][i],0);
			}
		}
	}
	if(pos[cntp]==n)write(g[0]);
	else if(!cntp)
	{
		int len=n,sum=mo(mo(mo((LL)(c-2)*(c-3)%mod*f[len-2][0]%mod+(LL)(c-2)*f[len-2][1]%mod)+(LL)(c-2)*f[len-2][2]%mod)+mo(f[len-2][3]+f[len-2][4]));
		write(sum);
	}
	else
	{
		int len=n-pos[cntp]+1,sum=mo(mo(mo((LL)(c-2)*(c-3)%mod*f[len-2][0]%mod+(LL)(c-2)*f[len-2][1]%mod)+(LL)(c-2)*f[len-2][2]%mod)+mo(f[len-2][3]+f[len-2][4]));
		write((LL)g[0]*sum%mod);
	}
	return 0;
}

一些感想

并不对劲的loj3111:p5359:[SDOI2019]染色

原文：https://www.cnblogs.com/xzyf/p/13086387.html