ARC149E Sliding Window Sort 做题记录

给定 $n,m,k$，考虑对某个 $n$ 的排列 $A$（标号 $0\sim n-1$）做如下操作：

• 从 $0$ 到 $k-1$ 枚举 $i$，把 $[A_{i\text{ mod }n},A_{(i+1)\text{ mod }n},A_{(i+2)\text{ mod }n},\dots,A_{(i+m-1)\text{ mod }n}]$ 拿出来升序排序再放回去；

给定一个 $n$ 的排列 $B$，求有多少个 $A$ 满足操作完后会变成 $B$。

$1\le m\le n\le 3\times 10^5$，$1\le k\le 10^9$。

由于 $k$ 很大，所以猜测操作很多次是没用的。

观察到若 $k>n-m+1$ 则后 $k-(n-m+1)$ 次操作相当于拉着前 $m-1$ 大值在转圈，所以这些操作是没用的，仅需把前 $m-1$ 大值复位即可归约到 $k=n-m+1$ 的情况。

不难发现 $k<n-m+1$ 的情况可以通过删掉操作没影响到的一段后缀来归约到 $k=n-m+1$ 的情况，所以仅需讨论 $k=n-m+1$ 情况下的做法。

不难发现，若 $B_{i-1}>B_i$ 则 $B_i$ 一定填入 $A_{i+m-1}$，否则：

• 若 $B_i$ 是前缀最大值，则其可以找 $A_{[1,i+m-1]}$ 中随便一个未填数的位置填入，有 $m$ 种方案；

• 若 $B_i$ 不是前缀最大值，则 $B_i$ 一定填入 $A_{i+m-1}$，证明如下：

  若 $B_{i-1}>B_i$ 则证明完毕，否则找到 $B_i$ 前面最靠后的 $>B_i$ 的 $B_j$，则 $B_i$ 一定不能填入 $A_{[j,j+m-1]}$。

  观察到 $B_j>B_{[j+1,i]}$，所以 $B_{j+1}$ 一定填入 $A_{j+m}$，$B_{j+2}$ 原本可以填入 $A_{[j+m,j+m+1]}$，可 $A_{j+m}$ 被占用，所以它只能填入 $A_{j+m+1}$。这样一直循环进行，最终 $A_{[j+m,i+m-2]}$ 均被占用，所以 $B_i$ 仅能填入 $A_{i+m-1}$。

  Q.E.D.

那么设 $B_{[0,k-1]}$ 有 $cnt$ 个前缀最大值，答案即为 $m^{cnt}(m-1)!$，最后的阶乘是因为最后一段的尾巴可以乱放。

时间复杂度 $O(n)$，注意 $0$ 的判断，代码如下：

#include <iostream>
#include <algorithm>
#include <cstdio>

using namespace std;

const int S=300005,p=998244353;

int n,m,k,a[S];
int b[S],c[S];

int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	if(k>n-m+1)
	{
		int lft=k-(n-m+1);
		int beg=((n-m+1)+lft)%n;
		for(int i=0;i<m-1;i++) b[i]=a[(beg+i)%n];
		int siz=n-m+1;
		for(int i=0;i<siz;i++) c[i]=a[(beg+m-1+i)%n];
		for(int i=0;i<siz;i++) a[i]=c[((i-lft)%siz+siz)%siz];
		for(int i=0;i<m-1;i++) a[siz+i]=b[i];
		k=n-m+1;
	}
	for(int i=0;i<n;i++) b[i]=a[i];
	sort(b+k-1,b+k-1+m);
	for(int i=k-1;i<=k-1+m-1;i++)
	{
		if(a[i]<a[k-1]||a[i]!=b[i]) return puts("0"),0;
	}
	int ans=1;
	for(int i=0;i<k;i++)
	{
		if(i==0||a[i]>a[i-1]) ans=1ll*ans*m%p;
		else a[i]=a[i-1];
	}
	for(int i=1;i<m;i++) ans=1ll*ans*i%p;
	printf("%d\n",ans);
	return 0;
}