• 欢迎光临~

CF1677 D Tokitsukaze and Permutations

开发技术 开发技术 2022-05-18 次浏览

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;
}
程序员灯塔
转载请注明原文链接:CF1677 D Tokitsukaze and Permutations
喜欢 (0)