CF1526 E. Oolimry and Suffix Array(从后缀数组反推字符串)

题目链接：https://codeforces.com/contest/1526/problem/E

题目大意：字符集大小为 $n$ ，询问有多少个字符串的后缀数组就是给定的后缀数组。

做法

其实我也不太清楚我是怎么想到这个做法的，反正就是想什么时候两个位置的字符能够相同，然后就知道怎么做了。

看到一个题解说的很有道理：https://www.luogu.com.cn/blog/namelessgugugu/solution-cf1526e

这么说的：知道 $s[i,n]<s[j,n]$ ，就知道 $s[i]\le s[j]$ ，问题是什么时候能够相等，显然是 $s[i+1,n]<s[j+1,n]$ 的时候能够相等。

所以做法就出来了：显然后缀数组上每个位置的字符是非严格递增的，问题是相邻的位置字符能否相等，显然条件就是上面那个，假设我们已经知道了至少需要有 $now$ 个不同的字符，则答案为：

$$\sum\limits_{i=0}^{\min(n,K)-now}\binom{K}{i+now}\binom{n-now}{i}$$

显然，这已经足以通过此题，但是还能再简化：

$$\begin{align*} &\sum\limits_{i=0}^{\min(n,K)-now}\binom{K}{i+now}\binom{n-now}{i}\\ =& \sum\limits_{i=0}^{\min(n,K)-now}\binom{K}{i+now}\binom{n-now}{n-now-i}\\ =& \sum\limits_{i=0}^{n}\binom{K}{i}\binom{n-now}{n-i}\\ \end{align*}$$

最后一步是因为超出来的范围都因为组合数不合法所以值为 $0$ ，不会对结果产生影响。

所以显然，最终化简结果为：$\binom{K+n-now}{n}$ 。

时间复杂度：$O(n+K)$ 。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+5;
const LL mod=998244353;
LL fc[N],nfc[N];
int n,K,sa[N],rk[N];
LL C(int x,int y){return fc[x]*nfc[y]%mod*nfc[x-y]%mod;}
int main(){
    scanf("%d%d",&n,&K);
    fc[0]=fc[1]=nfc[0]=nfc[1]=1;for(int i=2;i<=max(n,K);i++)nfc[i]=(mod-mod/i)*nfc[mod%i]%mod;
    for(int i=2;i<=max(n,K);i++)fc[i]=fc[i-1]*i%mod,nfc[i]=nfc[i-1]*nfc[i]%mod;
    for(int i=1;i<=n;i++){
        scanf("%d",&sa[i]);
        rk[sa[i]]=i;
    }
    // rk[n+1]=0;
    int now=1;
    for(int i=2;i<=n;i++){
        if(rk[sa[i-1]+1]>rk[sa[i]+1]){
            now++;
        }
    }
    LL ans=0;
    for(int i=0;i+now<=n && i+now<=K;i++){
        ans=(ans+C(K,i+now)*C(n-now,i))%mod;
    }
    printf("%lld\n",ans);
    return 0;
}