[原创]HDU 5635 LCP array

Tabris

CSDNhdu

发布于：2016年3月5日

次浏览

[原创]HDU 5635 LCP array

2016-03-05 22:57:14 Tabris_ 阅读数：573

博客爬取于 2020-06-14 22:45:01
以下为正文

版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/50811273

LCP Array

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 307 Accepted Submission(s): 86

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

题目就是说给你输入的 a[i]后 第 i 个字符与后面 a[i]个字符都是相同的 问你有多少个符合输入的种类
本题有主要有三个点
1.a[i]小于 n-i
2.a[i]是每一段递减的 而且必须是依次减 1 减到 0 后可以接着再有一段递减的 但最后都要到 1 否则不符合 1
3.每一段递减段的字符必须是相同的
可以把每一段规程一块 且相邻的两块不相同

Ps：取鱼之后的输出也超了 int 要用 long long int
博主在这里错了无数发才想到这个问题
最后正常写就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

# include <stdio.h>
const int MOD=1000000007;
int a[100005];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        scanf("%d",&n);
        long long int sum=26,mm=0;
        for(int i=1; i<n; i++)
        {
            scanf("%d",&a[i]);
        }
        for(int i=1; i<n; i++)
        {
            if(a[i]>n-i||a[i-1]!=0&&a[i]!=a[i-1]-1)
            {
                sum=0;
                break;
            }
            if(a[i]==0)
            {
                sum*=25;
                sum%=MOD;
            }
        }
        printf("%I64d\n",sum%MOD);
    }
    return 0;
}

本页文档最后更新于：2021年5月16日

CSDN

hdu

string

bestcoder

hdu5635