♥HDOJ 5635-LCP Array

た入场券 2022-08-21 00:04 16阅读 0赞

# LCP Array #

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)

Total Submission(s): 159 Accepted Submission(s): 47

Problem Description

Peter has a string  s=s![Image 1][]1![Image 1][]s![Image 1][]2![Image 1][]...s![Image 1][]n![Image 1][]![Image 1][], let  suff![Image 1][]i![Image 1][]=s![Image 1][]i![Image 1][]s![Image 1][]i\+1![Image 1][]...s![Image 1][]n![Image 1][]![Image 1][] be the suffix start with  i![Image 1][]\-th character of  s![Image 1][]. Peter knows the lcp (longest common prefix) of each two adjacent suffixes which denotes as  a![Image 1][]i![Image 1][]=lcp(suff![Image 1][]i![Image 1][],suff![Image 1][]i\+1![Image 1][])(1≤i<n![Image 1][]).  
  
Given the lcp array, Peter wants to know how many strings containing lowercase English letters only will satisfy the lcp array. The answer may be too large, just print it modulo  10![Image 1][]9![Image 1][]\+7![Image 1][].

Input

There are multiple test cases. The first line of input contains an integer  T![Image 1][] indicating the number of test cases. For each test case:  
  
The first line contains an integer  n![Image 1][] (  2≤n≤10![Image 1][]5![Image 1][])![Image 1][] \-- the length of the string. The second line contains  n−1![Image 1][] integers:  a![Image 1][]1![Image 1][],a![Image 1][]2![Image 1][],...,a![Image 1][]n−1![Image 1][]![Image 1][]  (0≤a![Image 1][]i![Image 1][]≤n)![Image 1][].  
  
The sum of values of  n![Image 1][] in all test cases doesn't exceed  10![Image 1][]6![Image 1][]![Image 1][].

Output

For each test case output one integer denoting the answer. The answer must be printed modulo  10![Image 1][]9![Image 1][]\+7![Image 1][].

Sample Input

3
    3
    0 0
    4
    3 2 1
    3
    1 2

Sample Output

16250
    26
    0

Source

[BestCoder Round \#74 (div.2)][BestCoder Round _74 _div.2]

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int a[1000000];
    int n;
    void f()
    {
    	int i,j;
    	long long ans=26;
    	for(i=1;i<n;i++)
    	{
    		if((a[i]-1)!=a[i+1]&&a[i]!=0)
    		{
    			printf("0\n");
    			return ;
    		}
    	}
    	int uu=0;
    	for(i=1;i<=n;i++)
    	{
    		if(a[i]==0)
    		{
    			if(uu>0)
    			{
    				ans*=25;
    				ans=ans%1000000007;
    			}
    			else
    			uu++;
    		}
    	}
    	printf("%I64d\n",ans);
    }
    int main()
    {
    	int t;
    	scanf("%d",&t);
    	while(t--)
    	{
    		scanf("%d",&n);
    		int i,j;
    		for(i=1;i<n;i++)
    		{
    			scanf("%d",&a[i]);
    		}
    		a[n]=0;
    		f();
    	}
    	return 0;
    }

[Image 1]: 
[BestCoder Round _74 _div.2]: http://acm.hdu.edu.cn/search.php?field=problem&key=BestCoder+Round+%2374+%28div.2%29&source=1&searchmode=source