CF1677D Tokitsukaze and Permutations

Tokitsukaze and Permutations

Description

有一个长度为 $n$ 的数组 $p$，将执行 $k$ 次操作。

操作过程：对于 $[1,n]$ 中，当$ p_{i} > p_{i+1}$，则交换 $p_{i}，p_{i+1}$。

经过 $k$ 次操作之后，得到了一个新数组 $a$，再定义数组 $v$ 表示在 $[1,i-1]$ 中比 $a_{i}$ 大的个数。

现在给定 $v$，但是有可能其中的值为 $-1$，这表示它的值并不确定 。

求有多少种 $p$ 满足在 $k$ 次操作后得到的 $v$ 和给定确定值一致，结果取模 $998244353$。

$1\le n\le 10^6$ 2s 250MB

Solution

大为震撼。

首先有一个结论 ：

  • 一个排列 $p$ 对应唯一的 $v$。

如果一个 $v$ 是合法的，当且仅当 $v_i\in [0,i-1]$。

再考虑每次操作的本质，把 $v_i$ 整体向左移一位，高位补 $0$，其他位置 $v_i\gets \max(v_i-1,0)$。

所以操作 $k$ 次以后，末尾 $k$ 个数为 $0$，如果不是就输出 $0$。

对于 $i\in [1,n-k]$ 中，考虑对答案的贡献：

  • 如果 $v_i$ 为 $-1$ ，操作 $k$ 次之前 $v_{i+k}$ 也是不知道的，可以取 $[0,i+k-1]$。
  • 如果 $v_i$ 为 $0$，操作 $k$ 次之前 $v_{i+k}\in[0,k]$。
  • 如果 $v_i>0$，操作 $k$ 次之前 $v_{i+k}=v_i+k$。是确定的。

所有贡献乘起来即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int n,v[maxn],p[maxn],k;
inline void solve(void) {
	int i,ans=1;
	read(n);read(k);
	for (i=1;i<=n;i++) read(v[i]);
	for (i=n;i>n-k;i--) if (v[i]>0) return puts("0"),void();
	for (i=n;i>k;i--) 
		if (v[i-k]==-1) ans=ans*i%mod;
		else if (v[i-k]==0) ans=ans*(k+1)%mod;
	for (i=1;i<=k;i++) ans=ans*i%mod;
	printf("%lld\n",ans);
}
signed main(void){
	int T;
	read(T);
	while (T--) solve();
	return 0;
}