hdu5635 BestCoder Round #74 (div.2)

LCP Array

Accepts: 131

Submissions: 1352

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 131072/131072 K (Java/Others)

问题描述

Peter有一个字符串 $s=s_{1}s_{2}...s_{n}$ , 令 $ext{suff}_i =s_{i}s_{i+1}...s_{n}$ 是 $s$ 第 $i$ 字符开头的后缀. Peter知道任意两个相邻的后缀的最长公共前缀 $a_i = ext{lcp}( ext{suff}_i, ext{suff}_{i+1}) quad (1 le i < n$ ).

现在给你数组 $a$ , Peter有多少个仅包含小写字母的字符串满足这个数组. 答案也许会很大, 你只要输出对 $10^9 + 7$ 取模的结果即可.

输入描述

输入包含多组数据. 第一行有一个整数 $T$ , 表示测试数据的组数. 对于每组数据:

第一行包含一个整数 $n$  ( $10^5)$ 表示字符串的长度. 第二行包含 $n - 1$ 个整数:  $a_1,a_2,...,a_{n-1}$   $a_i le n)$ .

所有数据中 $n$ 的和不超过 $10^6$ .

输出描述

对于每组数据, 输出答案对 $10^9+7$ 取模的结果.

输入样例

输出样例

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
");
        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
",ans%MOD);
        }
    }
    return 0;
}