提交记录

几乎是小常数的 $O(n\log n)$ 吧，本机对拍没问题，跑得比 $std$ 还快，一交上去除了特判点剩下全 TLE。

求 dalao 看下有没有什么复杂度假掉的地方或者其它玄学问题。尝试过在所有循环位置卡时依旧 TLE。

#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*=(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][5],ans;
int n,a[N][2],tp[N],p[N];
class arr{
	private:
		int tot,now,tim[N],lst[N*10];
		mint sum,atag[N*10],mtag[N*10];
		mint stag[N*10],v[N];
		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 get(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.get(u);y=f.get(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.get(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.get(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{
		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.get(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]&&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
*/