AT_nikkei2019_2_final_h

没人写题解，丢一篇来。

首先容易发现，若 $P$ 某些对应位置的限制之间有矛盾，则 $f(P)=0$，否则设 $c$ 为其中元素数量，则 $f(P)=m^{m-c}$。

发现 $Q_{P_i}=P_{i-len+1}$ 这样的限制相当于，每个在序列中的元素都和与它对称位置的元素形成双射。对称位置，很难不联想到回文串。回文串上的计数问题，很难不想到 manacher。

以下 $l,mid,r$ 均为 manacher 中记录的信息。

于是考虑这个问题是否为一个 manacher 能解决的问题。manacher 的核心操作就是，找到当前位置 $i$ 关于 $mid$ 的对称点，再将 $mid$ 的信息继承过来。那么到这题，容易发现是对双射后的结果在进行一次双射，显然还是一个双射，于是可以用 manacher 类似的方式处理。

然后具体考虑怎么处理。先处理合法的区间。设 $f_i$ 为 $i$ 点的最长合法半径。则若 $i+f_{mid\times 2-i}\le r$，则可以直接继承 $mid\times 2-i$ 的信息。

否则，发现如果按照常规的 manacher 一样，先将 $f_i$ 设为 $r-i$，我们则需要知道 $[i\times 2-r,r]$ 区间内的信息，才能继续往后推。但是我们显然是不知道的，怎么办呢？

此时发现一个性质：所有这样的超出 $r$ 的 $[r+1,i+f_{mid\times 2-i}]$ 的区间的长度总和不会超过 $n\times 2$。

证明：设 $j=mid\times 2-i$，首先如果想让上述区间尽可能大，$f_j$ 一定尽可能大，即 $j+f_j=r$。此时有；$i+f_j-r=l-(j-f_j)=2(mid-j)=2(i-mid)$。同时，处理完这 $f_i$ 后，$i+f_i\ge r$，一定可以把 $mid$ 设为 $i$，于是每次要处理的 $i+f_j-r$ 这一段长度 $\le$ 两倍的 $mid$ 的总移动次数，也就是 $2n$。得证。

于是，每次有 $i+f_j>r$ 时，先暴力地处理出 $f_j$ 去掉超出的部分后，得到的值，再依次尝试加入 $[r+1,i+f_j]$ 中的位置后是否合法。

但是此时我们只知道每个位置的最长合法半径，还没记录答案。但是很难不发现这是 trivial 的。对每个位置记录最长合法半径对应的答案，然后操作无非就是三种：继承某个位置的信息，或者加/删一个位置。随便维护一下就好了。

时间复杂度 $O(n)$ 或 $O(n\log n)$，取决于你是否预处理快速幂。我比较懒所以没预处理。

code：

int n,m,a[N],pre[N],suf[N],lst[N];
int c[N],f[N],g[N];
il int Mod(int x,int y){
	return x+y>=mod?x+y-mod:x+y;
}
il int qpow(int x,int y){
	int ret=1;
	while(y){
		if(y&1){
			ret=1ll*ret*x%mod;
		}
		x=1ll*x*x%mod,y>>=1;
	}
	return ret;
}
il bool check(int l,int r){
	if(l<1||r>n){
		return 0;
	}
	if(pre[r]<=l&&suf[l]>=r){
		return 1;
	}
	if(pre[r]>l){
		return a[l+r-pre[r]]==a[l];
	}
	return 0;
}
void Yorushika(){
	read(n,m);
	a[1]=0;
	rep(i,1,n){
		read(a[i+i]);
		a[i+i+1]=0;
	}
	n=n+n+1;
	rep(i,1,n){
		pre[i]=lst[a[i]];
		lst[a[i]]=i;
	}
	mems(lst,0x3f);
	drep(i,n,1){
		suf[i]=lst[a[i]];
		lst[a[i]]=i;
	}
	int mid=0,l=0,r=0,ans=0;
	rep(i,1,n){
		int p=mid*2-i;
		c[i]=1;
		if(a[i]){
			g[i]=qpow(m,m-1);
		}
		if(i<=r){
			f[i]=f[p],c[i]=c[p];
			g[i]=g[p];
			if(i+f[p]>r){
				rep(j,p-f[p],l-1){
					if(a[j]){
						g[i]=Mod(g[i],mod-qpow(m,m-c[i]+1));
					}
					if(suf[j]>p+p-j){
						c[i]--;
					}
					if(pre[p+p-j]<=j){
						c[i]--;
					}
				}
				rep(j,r+1,i+f[p]){
					if(!check(2*i-j,j)){
						f[i]=j-i-1;
						break;
					}
					if(pre[j]<=i+i-j){
						c[i]++;
					}
					if(suf[i+i-j]>j){
						c[i]++;
					}
					if(a[j]){
						g[i]=Mod(g[i],qpow(m,m-c[i]+1));
					}
				}
			}
		}
		if(i+f[i]>=r){
			mid=i,l=i-f[i],r=i+f[i];
		}
		while(check(i-f[i]-1,i+f[i]+1)){
			f[i]++;
			if(pre[i+f[i]]<=i-f[i]){
				c[i]++;
			}
			if(suf[i-f[i]]>i+f[i]){
				c[i]++;
			}
			if(a[i+f[i]]){
				g[i]=Mod(g[i],qpow(m,m-c[i]+1));
			}
			if(i+f[i]>=r){
				mid=i,l=i-f[i],r=i+f[i];
			}
		}
		ans=Mod(ans,g[i]);
	}
	printf("%d\n",ans);
}
signed main(){
	int t=1;
	//read(t);
	while(t--){
		Yorushika();
	}
}