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; }