Codeforces Round #723 Oolimry and Suffix Array 题解 (Java/C++)

题解

令原字符串为c。

首先我们可以注意到一个性质:对于i<j,那么一定有$c_{s[i]}\leq c_{s[j]}$。比如对于$[3,2,4,1,0,5,6]$,至少有$c_3\leq c_2\leq c_4\leq c_1\leq c_0\leq c_5\leq c_6$.

考虑字符串由n个不同的字符构成。那么我们只需要保证所选的字符,按照上面规则排列即可。因此,这种情况我们有$C_k^n$种解。(如果k<n,则为0种)

而当我们选择了小于n个字母,也就是这个字符串中一定有重复的字符。那么可以找到i和j满足:$i<j$且$c_{s[i]}=c_{s[j]}$。那么显然在排字典序时有:$c_{s[i] + 1}<c_{s[j]+1}$,或者$c_{s[i]+1}=c_{s[j]+1}$但$c_{s[i]+2}<c_{s[j]+2}$,以此类推。
但值得注意的是,如果$c_{s[i]+1}=c_{s[j]+1}$且$c_{s[i]+2}<c_{s[j]+2}$,那么在s中,s[i]+1的下标必然小于s[j]+1。
因此,对于$i<j$且$c_{s[i]}=c_{s[j]}$,当且仅当$index(s[i]+1)<index(s[j]+1)$。其中$index(x)$表示第x个后缀在s中的下标。

以$[3,2,4,1,0,5,6]$为例。我们发现$c_3<c_2$(也就是$c_3$不能等于$c_2$),因为$index(3+1)=index(4)=2>0=index(3)=index(2+1)$。 但$c_2\leq c_4$(也就是可以等于),因为$index(2+1)=index(3)=0<5=index(5)=index(4+1)$。
对于特殊的$c_5$和$c_6$。不难发现,在按字典序排序时,如果$c_5=c_6$,必然有$index(6)<index(5)$的前面,也就是字符串的结束符永远排在最前面,因此不妨令$index(n)=index(7)=-1$。
于是对于$[3,2,4,1,0,5,6]$我们有:$c_3< c_2\leq c_4< c_1\leq c_0\leq c_5<c_6$。

于是对于$[3,2,4,1,0,5,6]$,我们可以选择4个字母,也就是:$c_3< c_2= c_4< c_1= c_0=c_5<c_6$。也可以选择5个字母,也就是在3个可能相等的地方选择2处相等。也可以选择6个字母也就是3个可能相等的地方选择1处相等。

因此对于$[3,2,4,1,0,5,6]$,其结果为:$C_6^6\cdot C_3^1 + C_6^5\cdot C_3^2+C_6^4\cdot C_3^3=1\cdot3+6\cdot 3 + 15\cdot 1=36$。

代码

Java

Submission #117746690 - Codeforces
Codeforces. Programming competitions and contests, programming community

C++

Submission #117747120 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论