CF1526 Oolimry and Suffix Array 题解
namelessgugugu
·
·
题解
题意
给定长度为 n，字符集大小为 k 的字符串的 sa 数组（后缀数组）。求符合条件的字符串 S 的个数，对 998244353 取模。
#### Sol
先由 $sa$ 数组推出 $rk$ 数组，不难发现，如果 $rk_i > rk_j$，则 $S_i \geqslant S_j$，问题在于能不能取等。考虑到如果取等，在 $i$ 和 $j$ 代表的后缀对比大小时，将会忽视相同的第一位，从第二位开始比较，因此取等的条件是 $rk_{i+1} > rk_{j+1}$。我们只需对所有 $sa_i,sa_{i+1}$ 进行比较，就能确定整个字符串任意两个字符的大小关系，而且肯定合法。
接下来就是计算方案数，假设有 $m$ 个字符可以与它在 $sa$ 中的前一个字符取等号。每次有一个取了等，值不同的字符就减少一个，设有 $i$ 个取等，剩下的都不取等，则方案数为 $\tbinom{m}{i} \tbinom{k}{n-i}$，其中前者是选 $i$ 个取等的方案数，后者是给 $n-i$ 个字符赋不同值的方案数。
总方案数为 $\sum\limits^m_{i=0} \tbinom{m}{i} \tbinom{k}{n-i}$。这个已经可以算了。
由于 $m \leqslant n$，当 $i > m$ 时 $\tbinom{m}{i} = 0$，因此可以写成 $\sum\limits^n_{i=0} \tbinom{m}{i} \tbinom{k}{n-i} = \tbinom{m+k}{n}$。计算这个更简单，时间复杂度 $O(n+k)$。
#### AC代码
```cpp
#include <cstdio>
const int N = 200005, mod = 998244353;
int n, k, m, sa[N], rk[N], inv[N], ans = 1;
int main(void)
{
scanf("%d%d", &n, &k), rk[sa[0] = n+1] = 0, inv[1] = 1;
for(int i = 1;i <= n;++i)
scanf("%d", sa+i), rk[++sa[i]] = i;
for(int i = 2;i <= n;++i)
m += rk[sa[i]+1] > rk[sa[i-1]+1];
for(int i = m+k;i > m+k-n;--i)
ans = 1ll*ans*i%mod;
for(int i = 2;i <= n;++i)
ans = 1ll*ans*(inv[i] = 1ll*(mod-mod/i)*inv[mod%i]%mod)%mod;
//计算逆元同时更新答案
printf("%d\n", ans);
return 0;
}
```