LCP Array

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

hdu5635 BestCoder Round #74 (div.2)

给你n-1个数，每个数表示i,i+1开头的最长公共前缀，让你求出在只有

小写字母的情况下，最多有多少种可能

感觉自己最近问题很严重啊，

这题思路很快就看出来了，但是在细节上总是有问题

总共只有两种情况，这些数全部为0 或者 为公差为1的递减，可以 4 3 2 1 or

3 2 1 0 or 2 1 0 0；但是我在最后一位没有判断是否小于等于1，于是像

5 4 3 2便出现了问题- -

*/

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <map>

#include <algorithm>

using namespace std;

typedef long long ll;

#define LL(x) (x<<1)

#define RR(x) (x<<1|1)

#define MID(a,b) (a+((b-a)>>1))

const int maxn=125010;

int a[maxn];

const int MOD = 1e9 + 7;

int main()

{

    int t,n;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        for(int i =1; i < n; i++)

            scanf("%d",&a[i]);

        int flag = 0;

        int num = 0;

        for(int i = 1; i <= n-1; i++)

        {

            if(i == n-1)

            {

                if(a[i] > 1)

                    flag = 1;

                break;

            }

            if(a[i] != a[i+1]+1 && a[i] != 0)

                flag = 1;

        }

        if(flag)

            printf("0\n");

        else

        {

            ll ans = 26;

            int num = 0;

            for(int i = 1; i < n; i++)

            {

                if(a[i] == 0)

                {

                    ans = (ll)ans*25%MOD;

                }

            }

            printf("%I64d\n",ans%MOD);

        }

    }

    return 0;

}