P5359 [SDOI2019]染色 题解
SDNetFriend · · 题解
好毒瘤啊好毒瘤啊。
提供一种照搬 T1 的写法，并进一步解释细节。
题意这里不再赘述
P5359 [SDOI2019]染色
做法分析
思路几乎同 liuzhangfeiabc 大佬。
即朴素思路依旧考虑状态为
我们发现转移过程中我们主要需要考虑的是那些填了数的列，没填数的列本质完全相同，也只不过是个数值罢了。那我们可以考虑把状态修改成
既然状态设出来了吗，考虑转移。我们转移一定是依次考虑每一个填了数的列，那其实只需要考虑：前后两个填了数的列填的数的关系、中间有多少个没填数的列即可。
我们可以发现这个关系不会很多，可以总结成七种关系，有两对本质相同所以共五种本质不同的关系：
#0:a..a #1:a..b #2:a..a a..c #3:a..c a..b #4:a..b
b..b b..a b..c b..b b..a b..c c..d其中 a,b,c,d 表示了颜色的异同情况。确定了关系之后，再就需要考虑中间有多少空列，然后我们发现系数可以预处理，即设
那这个东西的预处理是
当然这个题最毒瘤的地方可能是在于细节巨多。
细节讨论
状态设计
首先对于这个状态
g 的转移
比较直观，这里举个例子，如 c 含义不同）
a..ca a..ba
b..ac b..cc然后考虑贡献我们要假定最后一列的 a,c 都已经确定下来，考虑倒数第二列这个自由的 c 有多少种情况。然后不难发现第一种情况 c 有 c 有
f 的转移
这估计是最麻烦的一部分了。
首先我们考虑
然后把判别分为两类，即当前列哪行填了颜色，前列哪行填了颜色，分成四种情况分别讨论。因为前面
然后通过判断我们可以得到当前列和前列两个确定的位置。然后我们再枚举当前列另一个不确定的位置（也有可能是已经确定的，不过按照原来的原则判掉就好了），于是我们发现这两列共四个位置我们已经确定了三个。然后最后一步就是根据已经确定的三个位置来讨论前列不同的不确定位置的贡献。
一般来讲情况是前列如果取某个特定的数是一种情况，不取这个特定的数是另一种情况。那么我们先求出前列所有
数据结构优化
改成数据结构优化之后，我们会发现如果当前列确定了两个的话，和确定一个的一概而论会比较难搞，于是我们考虑单独判一下当前列确定两个的情况。当然
然后根据之前
总结
可能是我一直追求代码的简洁，十分反感写太多的分类讨论。但这个题真的给我打回现实。有时分类讨论的好处就是讨论得深了确定的信息就多了，那样方便我们进一步的转移。
贴代码
关于码风可能挺奇怪的，我不大喜欢打多余空格，所以有的时候代码长得像砖头（雾）
另外 96 分代码有些诸如没有确定位置和确定位置不合法的特判没有判，但 100 分代码加上去了。
96 分代码
#include <bits/stdc++.h>
#define lint long long
#define sq(x) ((x)*(x))
using namespace std;
inline lint read(){
char c;lint f=1,res=0;
while(c=getchar(),!isdigit(c))if(c=='-')f*=-1;
while(isdigit(c))res=res*10+c-'0',c=getchar();
return res*f;
}
const lint md=1e9+9;
const int N=1e5+5;
struct mint{lint v;};//取模运算封装
inline mint operator+(mint x,mint y)
{x.v=((x.v+y.v)%md+md)%md;return x;}
inline mint operator-(mint x,mint y)
{y.v=-y.v;return x+y;}
inline void operator+=(mint &x,mint y)
{x=x+y;}
inline mint operator*(mint x,mint y)
{x.v=x.v*y.v%md;return x;}
inline mint operator*(lint x,mint y)
{y.v=y.v*x%md;return y;}
inline mint operator+(mint x,lint y)
{x.v=((x.v+y)%md+md)%md;return x;}
inline mint operator-(mint x,lint y)
{return x+(-y);}
inline void read(mint &x)
{x=mint{read()};}
mint c,g[N][5],f[2][N],ans;
int n,a[N][2],tp[N],p[N];
inline void init(){
g[0][1].v=g[0][3].v=g[0][4].v=1;
for(int i=1;i<=n;++i){//预处理 g
g[i][0]=g[i-1][1]+2*(c-2)*g[i-1][3]+(c-2)*(c-3)*g[i-1][4];
g[i][1]=g[i-1][0]+2*(c-2)*g[i-1][2]+(c-2)*(c-3)*g[i-1][4];
g[i][2]=g[i-1][1]+(c-2)*g[i-1][2]+(2*c-5)*g[i-1][3]+sq(c-3)*g[i-1][4];
g[i][3]=g[i-1][0]+(c-2)*g[i-1][3]+(2*c-5)*g[i-1][2]+sq(c-3)*g[i-1][4];
g[i][4]=g[i-1][0]+g[i-1][1]+2*(c-3)*(g[i-1][2]+g[i-1][3])+(c-3+sq(c-4))*g[i-1][4];
}
}
inline void solve(){
mint *pr,*cu;
pr=f[0];cu=f[1];//滚动数组+指针
lint lst=0;
for(int i=1;i<=n;++i){
if(!tp[i])continue;
lint s=i-lst-1;swap(cu,pr);
for(int i=0;i<=c.v;++i)
cu[i].v=0;
if(!lst){//当前列是第一个有确定数的列的情况
if(i==1){//如果当前列是第一列
if(tp[i]==1)//如果确定了一个数
for(int j=1;j<=c.v;++j)
{if(j!=a[i][p[i]])cu[j].v=1,++cu[0].v;}
else cu[a[i][1]].v=cu[0].v=1;
}else{--s;
if(tp[i]==1){//如果不是第一列且确定了一个数，这里就考虑第一列会有多少种情况，会产生什么样的贡献
int pos=p[i];
for(int j=1;j<=c.v;++j){
if(j==a[i][pos])continue;
cu[j]=g[s][0]+g[s][1]+2*(c-2)*(g[s][2]+g[s][3]);
cu[j]+=(c-2)*(c-3)*g[s][4];cu[0]+=cu[j];
}
}else{//确定两个数的情况同理
cu[a[i][1]]=g[s][0]+g[s][1]+(c-2)*(c-3)*g[s][4];
cu[a[i][1]]+=2*(c-2)*(g[s][2]+g[s][3]);cu[0]+=cu[a[i][1]];
}
}
}else{
int x,y;
for(int z=1;z<=c.v;++z){//分类讨论当前列和前列确定数的位置
if(a[i][0]){
x=a[i][0];if(z==x||(a[i][1]&&z!=a[i][1]))continue;//不满足要求就跳过
if(a[lst][0]){y=a[lst][0];
/* y..x
?..z *///分三种情况讨论
if(y==x)cu[z]=pr[z]*g[s][0]+(pr[0]-pr[z])*g[s][2];
else if(y==z)cu[z]=pr[x]*g[s][1]+(pr[0]-pr[x])*g[s][3];
else cu[z]=pr[x]*g[s][3]+pr[z]*g[s][2]+(pr[0]-pr[z]-pr[x])*g[s][4];
cu[0]+=cu[z];
}else{y=a[lst][1];
/* ?..x
y..z */
if(y==x)cu[z]=pr[z]*g[s][1]+(pr[0]-pr[z])*g[s][3];
else if(y==z)cu[z]=pr[x]*g[s][0]+(pr[0]-pr[x])*g[s][2];
else cu[z]=pr[x]*g[s][2]+pr[z]*g[s][3]+(pr[0]-pr[x]-pr[z])*g[s][4];
cu[0]+=cu[z];
}
}else{
x=a[i][1];if(z==x)continue;
if(a[lst][0]){y=a[lst][0];
/* y..z
?..x */
if(y==x)cu[z]=pr[z]*g[s][1]+(pr[0]-pr[z])*g[s][3];
else if(y==z)cu[z]=pr[x]*g[s][0]+(pr[0]-pr[x])*g[s][2];
else cu[z]=pr[x]*g[s][2]+pr[z]*g[s][3]+(pr[0]-pr[x]-pr[z])*g[s][4];
cu[0]+=cu[z];
}else{y=a[lst][1];
/* ?..z
y..x */
if(y==x)cu[z]=pr[z]*g[s][0]+(pr[0]-pr[z])*g[s][2];
else if(y==z)cu[z]=pr[x]*g[s][1]+(pr[0]-pr[x])*g[s][3];
else cu[z]=pr[x]*g[s][3]+pr[z]*g[s][2]+(pr[0]-pr[x]-pr[z])*g[s][4];
cu[0]+=cu[z];
}
}
}
}lst=i;
}
if(lst==n)ans=cu[0];
else{
lint s=n-lst-1;
for(int i=1;i<=c.v;++i)//处理最后一个有确定数的列不是n的情况
ans+=(g[s][0]+g[s][1]+2*(c-2)*(g[s][2]+g[s][3])+(c-2)*(c-3)*g[s][4])*cu[i];
}
}
int main(){
n=read();read(c);
for(int i=0;i<=1;++i)
for(int j=1;j<=n;++j)
a[j][i]=read();
for(int i=1;i<=n;++i){
if(!a[i][0]&&!a[i][1])tp[i]=0;
else if(a[i][0]&&a[i][1])tp[i]=2;
else tp[i]=1,p[i]=a[i][0]?0:1;
}init();solve();
printf("%lld",ans.v);
return 0;
}
/*
13 13
0 0 2 0 0 1 0 2 0 0 3 0 0
0 0 1 0 1 0 0 0 0 4 0 0 0
*/100 分代码
#include <bits/stdc++.h>
#define lint long long
#define sq(x) ((x)*(x))
using namespace std;
inline lint read(){
char c;lint f=1,res=0;
while(c=getchar(),!isdigit(c))if(c=='-')f*=-1;
while(isdigit(c))res=res*10+c-'0',c=getchar();
return res*f;
}
const lint md=1e9+9;
const int N=1e5+5;
struct mint{lint v;};//取模运算封装
inline mint operator+(mint x,mint y)
{x.v=((x.v+y.v)%md+md)%md;return x;}
inline mint operator-(mint x,mint y)
{y.v=-y.v;return x+y;}
inline void operator+=(mint &x,mint y)
{x=x+y;}
inline mint operator*(mint x,mint y)
{x.v=x.v*y.v%md;return x;}
inline void operator*=(mint &x,mint y)
{x=x*y;}
inline mint operator*(lint x,mint y)
{y.v=y.v*x%md;return y;}
inline mint operator+(mint x,lint y)
{x.v=((x.v+y)%md+md)%md;return x;}
inline mint operator-(mint x,lint y)
{return x+(-y);}
inline void read(mint &x)
{x=mint{read()};}
mint c,g[N*2][5],ans;
int n,a[N][2],tp[N],p[N],st;
class arr{//搬过来的 T1
private:
int tot,now,tim[N*10],lst[N*10];
mint sum,atag[N*10],mtag[N*10];
mint stag[N*10],v[N*10];
inline lint qpow(lint x,lint y){
lint res=1;
while(y){
if(y&1)res=res*x%md;
x=x*x%md;y>>=1;
}return res;
}
inline mint inv(lint x)
{return mint{qpow(x,md-2)};}
inline mint inv(mint x)
{return inv(x.v);}
inline void pushdown(int x){
if(lst[now]>tim[x])
v[x]=stag[lst[now]],tim[x]=lst[now];
mint _mul;
v[x]*=(_mul=mtag[now]*inv(mtag[tim[x]]));
v[x]+=atag[now]-atag[tim[x]]*_mul;
tim[x]=now;
}
public:
arr(){mtag[0].v=1;}
inline void set(int pos,mint val){
pushdown(pos);
sum+=val-v[pos];
v[pos]=val;
}
inline void mul(int pos,mint val){
pushdown(pos);
sum+=(val-1)*v[pos];
v[pos]*=val;
}
inline void add(int pos,mint val){
pushdown(pos);
sum+=val;v[pos]+=val;
}
inline void addall(mint val){
atag[now+1]=atag[now]+val;
mtag[now+1]=mtag[now];
lst[now+1]=lst[now];++now;
sum+=val*c;
}
inline void mulall(mint val){
if(!val.v){
++now;sum.v=0;lst[now]=now;
stag[now].v=0;mtag[now].v=1;
}else{
atag[now+1]=atag[now]*val;
mtag[now+1]=mtag[now]*val;
lst[now+1]=lst[now];++now;
sum=sum*val;
}
}
inline void setall(mint val){
++now;lst[now]=now;
stag[now]=val;mtag[now].v=1;
sum=val*c;
}
inline mint getv(int pos){
pushdown(pos);
return v[pos];
}
inline mint gsum()
{return sum;}
}f;
inline void init(){
g[0][1].v=g[0][3].v=g[0][4].v=1;
for(int i=1;i<=n;++i){
g[i][0]=g[i-1][1]+2*(c-2)*g[i-1][3]+(c-2)*(c-3)*g[i-1][4];
g[i][1]=g[i-1][0]+2*(c-2)*g[i-1][2]+(c-2)*(c-3)*g[i-1][4];
g[i][2]=g[i-1][1]+(c-2)*g[i-1][2]+(2*c-5)*g[i-1][3]+sq(c-3)*g[i-1][4];
g[i][3]=g[i-1][0]+(c-2)*g[i-1][3]+(2*c-5)*g[i-1][2]+sq(c-3)*g[i-1][4];
g[i][4]=g[i-1][0]+g[i-1][1]+2*(c-3)*(g[i-1][2]+g[i-1][3])+(c-3+sq(c-4))*g[i-1][4];
}
}
inline void solve(){
int lst=0;
for(int i=1;i<=n;++i){
if(!tp[i])continue;
int s=i-lst-1;
if(!lst){
if(i==1){
if(tp[i]==1)
for(int w=1;w<=c.v;++w)
{if(w!=a[i][p[i]])f.set(w,mint{1});}
else f.set(a[i][1],mint{1});
}else{--s;
if(tp[i]==1){
int pos=p[i];
for(int w=1;w<=c.v;++w){
if(w==a[i][pos])continue;
f.set(w,g[s][0]+g[s][1]+2*(c-2)*(g[s][2]+g[s][3]));
f.add(w,(c-2)*(c-3)*g[s][4]);
}
}else{
f.set(a[i][1],g[s][0]+g[s][1]+(c-2)*(c-3)*g[s][4]);
f.add(a[i][1],2*(c-2)*(g[s][2]+g[s][3]));
}
}
}else{
int u,v,w;
mint sum=f.gsum(),x,y;
if(tp[i]==2){//特判当前列确定两个的情况
u=a[i][0];w=a[i][1];
x=f.getv(u);y=f.getv(w);
f.setall(mint{0});
if(a[lst][0]){
v=a[lst][0];
if(v==u)f.set(w,y*g[s][0]+(sum-y)*g[s][2]);
else if(v==w)f.set(w,x*g[s][1]+(sum-x)*g[s][3]);
else f.set(w,x*g[s][3]+y*g[s][2]+(sum-x-y)*g[s][4]);
}else{
v=a[lst][1];
if(v==u)f.set(w,y*g[s][1]+(sum-y)*g[s][3]);
else if(v==w)f.set(w,x*g[s][0]+(sum-x)*g[s][2]);
else f.set(w,x*g[s][2]+y*g[s][3]+(sum-x-y)*g[s][4]);
}
}else if(a[i][0]){
u=a[i][0];x=f.getv(u);
if(a[lst][0]){
v=a[lst][0];
if(v==u)f.mulall(g[s][0]-g[s][2]),f.addall(sum*g[s][2]);
else f.mulall(g[s][2]-g[s][4]),f.addall(x*g[s][3]+(sum-x)*g[s][4]),f.set(v,x*g[s][1]+(sum-x)*g[s][3]);
}else{
v=a[lst][1];
if(v==u)f.mulall(g[s][1]-g[s][3]),f.addall(sum*g[s][3]);
else f.mulall(g[s][3]-g[s][4]),f.addall(x*g[s][2]+(sum-x)*g[s][4]),f.set(v,x*g[s][0]+(sum-x)*g[s][2]);
}f.set(u,mint{0});
}else{
u=a[i][1];x=f.getv(u);
if(a[lst][0]){
int v=a[lst][0];
if(v==u)f.mulall(g[s][1]-g[s][3]),f.addall(sum*g[s][3]);
else f.mulall(g[s][3]-g[s][4]),f.addall(x*g[s][2]+(sum-x)*g[s][4]),f.set(v,x*g[s][0]+(sum-x)*g[s][2]);
}else{
int v=a[lst][1];
if(v==u)f.mulall(g[s][0]-g[s][2]),f.addall(sum*g[s][2]);
else f.mulall(g[s][2]-g[s][4]),f.addall(x*g[s][3]+(sum-x)*g[s][4]),f.set(v,x*g[s][1]+(sum-x)*g[s][3]);
}f.set(u,mint{0});
}
}lst=i;
}
if(lst==n)ans=f.gsum();
else if(!lst){//特判没有确定数的情况
lint s=n-2;
ans=c*(c-1)*(g[s][0]+g[s][1]+2*(c-2)*(g[s][2]+g[s][3])+(c-2)*(c-3)*g[s][4]);
}else{
lint s=n-lst-1;
for(int i=1;i<=c.v;++i)
ans+=(g[s][0]+g[s][1]+2*(c-2)*(g[s][2]+g[s][3])+(c-2)*(c-3)*g[s][4])*f.getv(i);
}
}
int main(){st=clock();
n=read();read(c);
for(int i=0;i<=1;++i)
for(int j=1;j<=n;++j)
a[j][i]=read();
for(int i=1;i<=n;++i){//特判一定不合法的情况
if(a[i][0]&&a[i][1]&&a[i][0]==a[i][1])
return puts("0"),0;
if(i<n&&(a[i][0]&&a[i][0]==a[i+1][0]||a[i][1]&&a[i][1]==a[i+1][1]))
return puts("0"),0;
}
for(int i=1;i<=n;++i){
if(!a[i][0]&&!a[i][1])tp[i]=0;
else if(a[i][0]&&a[i][1])tp[i]=2;
else tp[i]=1,p[i]=a[i][0]?0:1;
}init();solve();
cout<<ans.v;
return 0;
}
/*
13 13
0 0 2 0 0 1 0 2 0 0 3 0 0
0 0 1 0 1 0 0 0 0 4 0 0 0
*/