描述
There is a strong data structure called “Suffix Array” which can effectively solve string problems.
Let S=s1s2…sn be a string and let S[i,j] denote the substring of S ranging from i to j. The suffix array A of S is now defined to be an array of integers providing the starting positions of suffixes of S in lexicographical order. This means, an entry A[i] is the starting position of the i-th smallest suffix in S and thus for all 1 < i ≤ n: S[A[i-1], n] < S[A[i], n].
For example: the suffix array of “banana” is [6, 4, 2, 1, 5, 3].
Here comes another problem called “Reverse Suffix Array”.
Given a suffix array, you need to figure out how many lower case strings are there whose suffix array is the same as the given suffix array.
输入
First line contains a positive number T which means the number of test cases.
For each test cases, first line contains a positive number N, the second line contains N integer(s) which indicates the suffix array A.
1 ≤ T ≤ 10, 1 ≤ N ≤ 100,000
1 ≤ A[i] ≤ N (i = 1…N)
输出
For each test case, output one line contains the answer. If no qualified string exists, output 0.
样例输入
1 5 4 3 2 5 1
样例输出
98280
题目大意是给后缀数组求原串有多少种可能性。
sa数组4 3 2 5 1可以画成下面：
④⑤
③④⑤
②③④⑤
⑤
①②③④⑤
首先可以得到$$④\le③\le②\le⑤\le①$$
但是其中有一些是小于号，需要从sa数组里判断。
对于sa数组相邻两行，例如④和③，
想要知道是\(④\le③\)还是\(④<③\)，只需比较他们的后一段的大小，即⑤和④⑤的大小，这个可以从sa数组里直接查出来。 若\(⑤>④⑤\)，那么\(④<③\)，否则\(④\le③\)。这是本题的关键。
判断完后我们得到\[④<③\le②<⑤\le①\]
转化为求\(1\le④<③\le②<⑤\le①\le26\)的整数解的问题，这是个经典的插板问题。
做一步映射变为\(1\le④<③<②+1<⑤<①+2\le26\)，
设原来中间有k个\(“\le”\)，那么解的数量就是\(\binom{26+k}{n}\)。
大数的问题用java或者python搞一下就好了。
cas=int(input()) for cs in range(cas): n=int(input()) sa=list(map(lambda x:x-1,map(int,raw_input().split()))) ind=[0]*(n+1) ind[n]=-1 for i in range(n): ind[sa[i]]=i sum=0 for i in range(n-1): if ind[sa[i]+1]>ind[sa[i+1]+1] : sum+=1 if(sum>25):print(0) else: k=n-1-sum ans=1 for i in range(26+k,n,-1):ans*=i for i in range(1,26+k-n+1):ans/=i print(ans)