CF1677 D Tokitsukaze and Permutations

传送门：https://codeforc.es/contest/1677/problem/D

官方题解：https://codeforc.es/contest/1677/attachments/download/16092/Codeforces Round 789 Chinese Tutorial.pdf

考虑一个未进行过操作的排列 (P)，以及其 (v) 序列。

定义一个 (v) 序列合法，当且仅当存在至少一个 (P) 与其对应。

容易发现 (P) 与 (v) 其实是一一对应的。

证明：

给定一个 (P) 数组，我们能根据定义求出唯一一个 (v)。

给定一个合法 (v) 数组，显然我们能通过 (v_n) 知道 (P_n) 的值，然后就能通过 (v_{n-1}) 知道 (P_{n-1}) 的值。以此类推，我们能够确定 (P)。

得证。

所以我们可以直接对 (v) 进行计数。

同样的我们考虑怎样的 (v) 序列是合法的。不难发现如果对于任意 (v_i) 有 (v_i<i)。那么 (v) 是合法的。

证明：

当 (v) 的长度为 (1) 时显然成立。

假设当 (v) 的长度为 (n-1) 时成立。设 (v) 是一个长为 (n) 的序列，(P) 是一个长为 (n-1) 的序列，且与 (v) 的前 (n-1) 项构成的 (v') 对应。

当 (v_nge n) 时，显然不合法，当 (v_n<n) 时，我们将 (v_n+1) 这个数放到 (P_n)。然后将 (n) 这个数放在 (P) 中 (n-1) 这个数的位置，将 (n-1) 放到 (n-2) 的位置，以此类推。我们得到了一个新的序列 (P')。

显然 (P') 与 (v) 对应。

证毕。

因此我们可以考虑对 (v) 计数。

我们发现进行一次操作就是相当于对原序列做一次冒泡排序。

观察 (v) 的变化。发现 (v) 序列的变化相当于先使 (v_i=max(v_i-1,0))，再将整个 (v) 序列左移，让 (v_1) 直接被覆盖，(v_n) 等于 (0)。

设 (V) 为输入的 (v) 序列。(v) 为我们计数的序列。

显然 (v_i,iin[1,k]) 的取值有 (i) 种可能，是 ([0,i-1])。

对于 (v_i,iin[k+1,n])。如果 (V_{i-k}=-1) 则 (v_i) 的取值有 (i) 种，如果 (V_{i-k}=0) 则 (v_i-kle 0)。所以 (v_{i}) 取值有 (k+1) 种。而当 (0<V_{i-k}< i+k) 时，(v_i) 取值确定。当 (V_{i-k}ge i-k) 时，则满足条件的 (v) 序列不存在。

对于 (V_i,iin[n-k+1,n])，如果 (V_i) 不等于 (0) 或 (-1)。则满足条件的 (v) 序列也不存在。

将所有 (v) 序列可能取值的情况数相乘即可。

复杂度 (O(n))。

代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e6+5;
const int MOD = 998244353;
int n,k,V[MAXN];
int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		scanf("%d %d",&n,&k);
		for(int i=1;i<=n;++i) scanf("%d",&V[i]);
		ll Ans=1;
		for(int i=1;i<=k;++i) Ans=Ans*i%MOD;
		for(int i=k+1;i<=n;++i)
		{
			if(V[i-k]==0) Ans=Ans*(k+1)%MOD;
			if(V[i-k]==-1) Ans=Ans*i%MOD;
			if(V[i-k]>=i-k) Ans=0;
		}
		for(int i=n-k+1;i<=n;++i) if(V[i]!=0&&V[i]!=-1) Ans=0;
		printf("%lldn",Ans);
	}
	return 0;
}