hdoj LCP Array 5635 （找规律）

）、英雄互娱（杭州）

LCP Array Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 1310    Accepted Submission(s): 373 Problem Description Peter has a string   s=s1s2...sn , let   suffi=sisi+1...sn  be the suffix start with   i -th character of   s . Peter knows the lcp (longest common prefix) of each two adjacent suffixes which denotes as   ai=lcp(suffi,suffi+1)(1≤i<n ). 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   109+7 .   Input There are multiple test cases. The first line of input contains an integer   T  indicating the number of test cases. For each test case: The first line contains an integer   n  ( 2≤n≤105)  -- the length of the string. The second line contains   n−1  integers:   a1,a2,...,an−1   (0≤ai≤n) . The sum of values of   n  in all test cases doesn't exceed   106 .   Output For each test case output one integer denoting the answer. The answer must be printed modulo   109+7 . Sample Input 3 3 0 0 4 3 2 1 3 1 2 Sample Output 16250 26 0 问题描述 Peter有一个字符串s=s_{1}s_{2}...s_{n}s=s​1​​s​2​​...s​n​​, 令\text{suff}_i =s_{i}s_{i+1}...s_{n}suff​i​​=s​i​​s​i+1​​...s​n​​是ss第ii字符开头的后缀. Peter知道任意两个相邻的后缀的最长公共前缀a_i = \text{lcp}(\text{suff}_i, \text{suff}_{i+1}) \quad (1 \le i < na​i​​=lcp(suff​i​​,suff​i+1​​)(1≤i<n). 现在给你数组aa, Peter有多少个仅包含小写字母的字符串满足这个数组. 答案也许会很大, 你只要输出对10^9 + 710​9​​+7取模的结果即可. 输入描述 输入包含多组数据. 第一行有一个整数TT, 表示测试数据的组数. 对于每组数据: 第一行包含一个整数nn (2 \le n \le 10^5)2≤n≤10​5​​)表示字符串的长度. 第二行包含n - 1n−1个整数: a_1,a_2,...,a_{n-1}a​1​​,a​2​​,...,a​n−1​​ (0 \le a_i \le n)(0≤a​i​​≤n). 所有数据中nn的和不超过10^610​6​​. 输出描述 对于每组数据, 输出答案对10^9+710​9​​+7取模的结果. 输入样例 3 3 0 0 4 3 2 1 3 1 2 输出样例 16250 26 0 //思路： 找规律，如果第一位是个数，那么他后面的几位数一定是逐位递减的，直到为0， 这也说明了有数的这几位是相同的字母，为0的位置可以存放25种字母（只要不 与它前面的数相同就行了。）找到这个规律就好解决了。 #include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #include<iostream> #include<queue> #define INF 0x3f3f3f3f #define IN __int64 #define ull unsigned long long #define ll long long #define N 1000010 #define M 1000000007 using namespace std; int a[N]; int main() { int t,n,i; scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=1;i<n;i++) scanf("%d",&a[i]); a[n]=0; ll ans=26; int flag=0; for(i=1;i<n;i++) { if(a[i]&&(a[i+1]!=a[i]-1)) { flag=1; break; } } int kk=0; for(i=1;i<=n;i++) { if(!a[i]) { if(kk>0) ans=(ans*25)%M; else kk++; } } if(flag) printf("0\n"); else printf("%lld\n",ans); } return 0; }