CF1526E Oolimry and Suffix Array 做题记录

给定 $n$ 和字符集大小 $k$ 以及一个 $0\sim n-1$ 的排列 $sa$，求有多少个长 $n$，字符集大小 $k$ ，从 $0$ 开始标号的字符串 $s$ 满足把 $a=\{0,1,2,\dots,n-1\}$ 按照 $s_{[i,n-1]}$ 字典序排序后满足 $a=sa$。

即生成的后缀数组是 $sa$。

$1\le n,k\le 2\times 10^5$。

首先设 $rk$ 为满足 $sa_{rk_i}=i$ 的数组，即 $s_{[i,n-1]}$ 的排名。

那么观察 $sa_i$ 和 $sa_{i+1}$，必有 $s_{sa_i}\le s_{sa_{i+1}}$。考虑什么时候能取到等号，显然 $rk_{sa_i+1}<rk_{sa_{i+1}+1}$ 时才行。

那么统计出能取等号的位置个数 $cnt$，则答案为 $\sum\limits_{i=0}^{cnt}\binom{cnt}{i}\binom{k}{n-i}=\binom{cnt+k}{n}$。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=400005,p=998244353;

int n,k,a[S],b[S];
int fra[S],inv[S];

inline int qpow(int x,int y)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=y&1?1ll*res*x%p:res;
	return res;
}

inline int C(int n,int m)
{
	if(n<m) return 0;
	return 1ll*fra[n]*inv[n-m]%p*inv[m]%p;
}

int main()
{
	fra[0]=1;
	for(int i=1;i<=S-3;i++) fra[i]=1ll*fra[i-1]*i%p;
	inv[S-3]=qpow(fra[S-3],p-2);
	for(int i=S-3;i>=1;i--) inv[i-1]=1ll*inv[i]*i%p;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[++a[i]]=i;
	b[n+1]=0;
	int cnt=0;
	for(int i=1;i<=n-1;i++) cnt+=b[a[i]+1]<b[a[i+1]+1];
	printf("%d\n",C(cnt+k,n));
	return 0;
}