hihoCoder 1579 : 统计后缀数组相同的字符串个数

今年北京网赛出了一道字符串计数论文题hihoCoder 1579，简单来说就是给定一个后缀数组，统计有多少个仅含小写字母的字符串的后缀数组和它一样。

既然有论文，那就来学习一下咯。论文叫Counting suffix arrays and strings，里面有大段大段看不懂的数学证明，我这里就大概说下结论吧。

令$P[]$为一长度为$n$的后缀数组（此时$P[]$是$n$的一个排列）。
令$R[]$表示$P[]$对应的rank数组。$R[i]=j$当且仅当$P[j]=i$。
令$R[n+1]=0$，并定义数组$R_+[]$，$R_+[i] = R[P[i]+1] \ (1 \leq i \leq n)$。
定义集合$U = \{i | i \in [1,n-1], R_+[i] > R_+[i+1] \}$，并令$d = |U|$。
最后再设字符集大小为$\sigma$。

那么我们有如下结论：

定理1（原文定理4）：长度为$n$且对应的后缀数组为$P$的所有字符串的个数为$\binom{n+\sigma-d-1}{\sigma-d-1}$。
注意公式中的$\sigma-d-1$需满足非负，若$d>\sigma-1$，则满足条件的字符串不存在（个数为0）。

定理2（原文定理5）：长度为$n$且对应的后缀数组为$P$的所有字符串中，满足恰由$k \ (k \leq \sigma)$种不同的字符组成的字符串的个数为$\binom{n-d-1}{k-d-1}$。
和定理1类似，若$d > k-1$，则满足条件的字符串不存在。

有了上述定理1的结论，我们就能圆满解决这道题目了。话说定理2也能拿来出题报复社会，而且出题思路感觉比定理1要灵活一些。

hihoCoder 1579的代码：

import java.io.*;
import java.util.*;
import java.math.*;

public class Main {
    static final int maxn = (int)1e5;
    static BigInteger Calc(int l, int r) {
        BigInteger res = BigInteger.ONE;
        for(int i = l; i <= r; ++i)
            res = res.multiply(BigInteger.valueOf(i));
        return res;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt(), n, u;
        int[] P = new int[maxn + 5], R1 = new int[maxn + 5];
        for(; T > 0; --T) {
            n = in.nextInt();
            for(int i = 1; i <= n; ++i) {
                P[i] = in.nextInt();
                R1[P[i]] = i;
            }
            int dd = 0;
            R1[n + 1] = 0;
            for(int i = 1; i < n; ++i)
                if(R1[P[i] + 1] > R1[P[i + 1] + 1])
                    ++dd;
            if(dd > 25) { System.out.println("0"); continue; }
            int n1 = n + 26 - dd - 1, n2 = 26 - dd - 1;
            System.out.println(Calc(n1 - n2 + 1, n1).divide(Calc(1, n2)));
        }
    }
}