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.

样例输入

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)

 

发表回复

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