2017ICPC北京网络赛 B | hihocoder 1579 Reverse Suffix Array

描述

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.

样例输入

样例输出

 

题目大意是给后缀数组求原串有多少种可能性。

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搞一下就好了。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注