精华内容
下载资源
问答
  • LCP

    千次阅读 2017-03-14 19:24:30
    LCP总结。

    定义

    LCP,最长公共前缀(并不是LCS最长公共子序列),这货其实一般是对于一个字符串的后缀而言的。

    基于后缀数组的LCP

    思想

    因为和后缀有关,所以在后缀数组的基础上实现。

    实现

    定义H[i]表示SA[i-1]和SA[i]的最长公共前缀,rank[i]表示i的名次,那么不难发现SA[i]和SA[j](i<j)的最长公共前缀就是H[i+1],H[i+2],H[i+3],……,H[j]中的最小值,也就是RMQ问题!RMQ问题我们有办法快速求得,现在唯一的问题就是这个H数组怎么构造。

    O(n^2)的算法很容易想到,但是立刻让之前辛辛苦苦的倍增算法白费了。所以我们需要另想办法,先用aaaabbaaab举个例子:

    1  aaaabbaaab
    7  aaab         H[2]=3 h[7]=3
    2  aaabbaaab    H[3]=3 h[2]=3
    8  aab          H[4]=2 h[8]=2
    3  aabbaaab     H[5]=3 h[3]=3
    9  ab           H[6]=1 h[9]=1
    4  abbaaab      H[7]=2 h[4]=2
    10 b            H[8]=0 h[10]=0
    6  baaab        H[9]=1 h[6]=1
    5  bbaaab       H[10]=1 h[5]=1
    

    求7(SA[2])和9(SA[6])的公共前缀,那么就是min(3,2,3,1)=1。

    设h[i]=H[rank[i]],我们发现,h[i]>=h[i-1]-1!这难道是巧合吗?不是的,我们可以证明得到:(k是SA[rank[i-1]-1],也就是排序过后i-1的前一个)
    这里写图片描述
    ①当h[i-1]>1时
    因为h[i-1]>1,说明至少有2个匹配到了。我们现在把第一个删除,就可以得到后缀k+1和i,那么后缀k+1肯定在i前面。显然SA[rank[k+1]]SA[rank[i]]之间所有的后缀的前h[i-1]-1位是和k+1和i一样的(想一想,为什么)。又因为SA[rank[k+1]]SA[rank[i]]的最长公共前缀是最小的h,所以每一个h都>=h[i-1]-1,由此得到h[i]>=h[i-1]-1。

    下面给出示意图:
    这里写图片描述

    ②当h[i-1]<=1时
    之前k+1一定在i前面,而当h[i-1]<=1时,k+1就不一定在i前面了(因为把LCP删光了)。这种情况怎么办?我们换一种思路证明:因为h[i-1]<=1,所以h[i-1]-1<=0。又因为h[i]>=0,所以h[i]>=h[i-1]-1。

    既然知道了这个性质,那么我们就算h,然后把h送给对应的H,这样就可以把H数组构造完成了。至于RMQ问题,就不需要多说了。

    模板

    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const int maxl=200000,maxt=18;
    
    int len,SA[maxl+5],rk[maxl+5],t[maxl+5],ha[maxl+5],H[maxl+5],RMQ[maxl+5][maxt+5];
    char now[maxl+5];
    
    void make_SA(char* s)
    {
    	int MAX=0;len=strlen(s+1);
    	memset(ha,0,sizeof(ha));
    	for (int i=1;i<=len;i++) {ha[rk[i]=s[i]]++;if (rk[i]>MAX) MAX=rk[i];}
    	for (int i=1;i<=MAX;i++) ha[i]+=ha[i-1];
    	for (int i=len;i>=1;i--) SA[ha[rk[i]]--]=i;
    	for (int k=1;k<=len;k<<=1)
    	{
    		int p=0;
    		for (int i=len-k+1;i<=len;i++) t[++p]=i;
    		for (int i=1;i<=len;i++) if (SA[i]>k) t[++p]=SA[i]-k;
    		memset(ha,0,sizeof(ha));
    		for (int i=1;i<=len;i++) ha[rk[t[i]]]++;
    		for (int i=1;i<=MAX;i++) ha[i]+=ha[i-1];
    		for (int i=len;i>=1;i--) SA[ha[rk[t[i]]]--]=t[i];
    		memcpy(t,rk,sizeof(t));
    		p=1;rk[SA[1]]=1;
    		for (int i=2;i<=len;i++)
    			if (t[SA[i-1]]==t[SA[i]]&&t[SA[i-1]+k]==t[SA[i]+k]) rk[SA[i]]=p; else rk[SA[i]]=++p;
    		if (p==len) break;
    		MAX=p;
    	}
    }
    void make_H() //处理H数组
    {
    	int k=0;
    	for (int i=1;i<=len;i++)
    	{
    		if (k) k--;int j=SA[rk[i]-1];if (j==0) continue;
    		while (now[i+k]==now[j+k]) k++;
    		RMQ[rk[i]][0]=H[rk[i]]=k;
    	}
    	int ln=log2(len); //RMQ
    	for (int j=1;j<=ln;j++)
    	for (int i=1;i<=len-(1<<j)+1;i++)
    		RMQ[i][j]=min(RMQ[i][j-1],RMQ[i+(1<<j-1)][j-1]);
    }
    int LCP(int x,int y) //求后缀x和后缀y的LCP
    {
    	x=rk[x];y=rk[y];if (x>y) swap(x,y);x++;int j=log2(y-x+1);
    	return min(RMQ[x][j],RMQ[y-(1<<j)+1][j]);
    }
    bool Eoln(char ch) {return ch==10||ch==13||ch==EOF;}
    int reads(char* s)
    {
    	int len=0;
    	char ch=getchar();if (ch==EOF) return 2;
    	s[++len]=ch;while (!Eoln(s[len])) s[++len]=getchar();s[len--]=0;
    	return 0;
    }
    void writei(int x,bool fl=false)
    {
    	if (x==0) {if (fl==false) putchar('0');return;}
    	writei(x/10,true);putchar(x%10+48);
    }
    int main()
    {
    	freopen("LCP.in","r",stdin);
    	freopen("LCP.out","w",stdout);
    	reads(now);make_SA(now);make_H();
    	return 0;
    }
    

    基于哈希的LCP

    ps:学习刘汝佳大神(Orz,%%%)蓝书上LCP之后写的

    思想

    如何快速比较字符串?有一种方法是Hash,所以求LCP时的验证可以用Hash实现。
    ps:当然,Hash有风险,可能会判断错误,不过错误概率比较小。如果一些LCP问题能用稳定方法(如后缀数组)解决,就尽量不要用基于哈希的LCP。

    实现

    比如这样的一个字符串(len为5),我们构造一个H(i)表示i~len哈希值:
    abcde (ASCII码为97 98 99 100 101)

    H(5)=101
    H(4)=H(5)*Base+100=101*Base+100
    H(3)=H(4)*Base+99=101*Base^2+100*Base+99
    H(2)=H(3)*Base+98=101*Base^3+100*Base^2+99*Base+98
    H(1)=H(2)*Base+97=101*Base^4+100*Base^2+99*Base^2+98*Base+97
    

    (毕竟是哈希……Base乱取即可)
    有一个问题就是素数怎么取比较好?刘汝佳大神表示可以放在unsigned long long里让H自然溢出,就不需要特别选个素数了。

    定义Hash(i,len)为从i位开始,向右推len位(包括i)的哈希值,不难发现:
    Hash(i,len)=H(i)−H(i+len)∗xlenHash(i,len)=H(i)-H(i+len)*x^{len}Hash(i,len)=H(i)H(i+len)xlen

    预处理H(i)和x^len之后就可以很快求出Hash值。求i和j的LCP,只需要二分枚举长度len,判断Hash(i,len)是否和Hash(j,len)相同就行了。

    展开全文
  • LCP Array

    2017-07-28 00:41:28
    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 ...
  • Moby lcp integration

    2020-11-29 09:36:39
    <div><p>Integration of LCP solvers from Evan Drumwright's Moby project into Drake optimization tree. Per #1772 </p><p>该提问来源于开源项目:RobotLocomotion/drake</p></div>
  • LCP 模板

    2019-01-01 14:33:00
    LCP Description 给定串 \(S\) . \(m\) 组询问 \((X, Y, L, R)\): 求 \(S[X,Y]\) 与 \(S[L,R]\) 的最长公共前缀. Input 第一行一个串 \(S\). 第二行一个数 \(m\). 接下来 \(m\) 行, 每行 \(4\) 个数 \(X, Y, L, R\)....

    LCP

    Description

    给定串 \(S\) .

    \(m\) 组询问 \((X, Y, L, R)\): 求 \(S[X,Y]\)\(S[L,R]\) 的最长公共前缀.

    Input

    第一行一个串 \(S\).

    第二行一个数 \(m\).

    接下来 \(m\) 行, 每行 \(4\) 个数 \(X, Y, L, R\).

    Output

    输出共 \(m\) 行, 第 \(i\) 行为第 \(i\) 个询问的答案.

    HINT

    \(1 <= |S| <= 100000\), 且 \(S\) 由小写字母构成.

    \(1 <= m <= 100000\)

    \(1 <= L <= R <= |S|\)

    \(1 <= X <= Y <= |S|\)


    LCP标准模板,放一下...

    Code:

    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    using std::min;
    const int N=1e5+10;
    char s[N];
    int tax[N],Rank[N],sa[N],sec[N];
    int n,m,q,st[N][20],h[N],height[N],Log[N];
    void Rsort()
    {
        for(int i=1;i<=m;i++) tax[i]=0;
        for(int i=1;i<=n;i++) ++tax[Rank[i]];
        for(int i=2;i<=m;i++) tax[i]+=tax[i-1];
        for(int i=n;i;i--) sa[tax[Rank[sec[i]]]--]=sec[i];
    }
    bool cmp(int x,int y,int len){return sec[x]==sec[y]&&sec[x+len]==sec[y+len];}
    void SuffixSort()
    {
        for(int i=1;i<=n;i++) Rank[i]=s[i]-'a'+1,sec[i]=i;
        m=26,Rsort();
        for(int p=0,w=1;p<n;w<<=1,m=p)
        {
            p=0;for(int i=n-w+1;i<=n;i++) sec[++p]=i;
            for(int i=1;i<=n;i++) if(sa[i]>w) sec[++p]=sa[i]-w;
            Rsort(),std::swap(Rank,sec),Rank[sa[p=1]]=1;
            for(int i=2;i<=n;i++) Rank[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;
        }
        Log[0]=-1;
        for(int k,i=1;i<=n;height[Rank[i]]=h[i],Log[i]=Log[i>>1]+1,st[i][0]=i,++i)
            for(k=sa[Rank[i]-1],h[i]=h[i-1]?h[i-1]-1:0;s[i+h[i]]==s[k+h[i]];++h[i]);
        for(int j=1;j<=17;j++)
        {
            for(int i=1;i<=n-(1<<j)+1;i++)
            {
                int x=st[i][j-1],y=st[i+(1<<j-1)][j-1];
                st[i][j]=height[x]<height[y]?x:y;
            }
        }
    }
    int query(int l,int r)
    {
        if(l>r) std::swap(l,r);
        if(++l==r) return height[st[l][0]];
        int d=Log[r+1-l],x=st[l][d],y=st[r-(1<<d)+1][d];
        return height[x]<height[y]?height[x]:height[y];
    }
    int main()
    {
        scanf("%s",s+1),n=strlen(s+1);
        SuffixSort();
        scanf("%d",&q);
        for(int x,y,l,r,i=1;i<=q;i++)
        {
            scanf("%d%d%d%d",&x,&y,&l,&r);
            if(x==l) printf("%d\n",min(r,y)+1-l);
            else printf("%d\n",min(query(Rank[x],Rank[l]),min(r+1-l,y+1-x)));
        }
        return 0;
    }

    2019.1.1

    转载于:https://www.cnblogs.com/butterflydew/p/10204769.html

    展开全文
  • LCP parsing issue

    2020-11-27 14:37:16
    The LCP parser cannot parse some LCP files, because they contain a 'PerspectiveModel' section in the XML attributes. For example, profile "Adobe (Apple iPhone 7 back camera 3.99mm f/1.8)&...
  • PPP LCP原理

    2020-12-15 14:42:20
    链路控制协议,简称LCP(Link Control Protocol)。它是PPP协议的一个子集,用来建立、拆除和监控PPP数据链路,完成二层协商。 LCP协议报文格式: Code域 • 代码域的长度为一个字节,主要是用来标识LCP数据报文的...

    概念:

    链路控制协议,简称LCP(Link Control Protocol)。它是PPP协议的一个子集,用来建立、拆除和监控PPP数据链路,完成二层协商。

    LCP协议报文格式:

    在这里插入图片描述
    Code域
    • 代码域的长度为一个字节,主要是用来标识LCP数据报文的类型。

    Identifier域
    • 标识域为1个字节,用来匹配请求和响应,当标识域值为非法时,该报文将被丢弃。
    • 通常一个配置请求报文的ID是从0x01开始逐步加1的。当对端接收到该配置请求报文后,无论使用何种报文回应对方,但必须要求回应报文中的ID要与接收报文中的ID一致。例如我这端发送的是1,对方也需要回复1。

    Length域
    • 长度域的值就是该LCP报文的总字节数据。它是代码域、标志域、长度域和数据域四个域长度的总和(不包括FCS域和填充域)。
    • 长度域所指示字节数之外的字节将被当作填充字节而忽略掉,而且该域的内容不能超过MRU的值,最大为1500字节。

    Data域
    • Type为协商选项类型。
    • Length为协商选项长度,它是指Data域的总长度,也就是包含Type、Length和Data。
    • Data为协商的选项具体内容。

    LCP协议有3大类报文:

    1.链路配置包,用于建立和配置链路: Configure-Request(匹配请求),Configure-Ack(匹配确认),Configure-Nak(匹配否认),和Configure-Reject(匹配拒绝)。
    在这里插入图片描述
    当通信双方需要建立链路时,无论哪一方都需要发送Config-Request报文并携带每一端自已所希望协商的配置参数选项。下表为可选的配置参数选项:
    在这里插入图片描述
    可以简单的说明一下比较重要的用于协商的参数:
    在这里插入图片描述
    认证协议:PPP和CHAP

    魔术字作用:防止环路(具体步骤在最后)

    config-request报文:
    在这里插入图片描述
    config-ack报文:
    在这里插入图片描述
    2.链路结束包,用于结束一个链路: Terminate-Request(终止请求) 和 Terminate-Ack(终止确认)。

    LCP报文中提供了一种机制来关闭一个点对点的连接,想要关断链路的一端A会持续发送Terminate-Request报文,直到收到一个Terminate-Reply为止。接收端B一旦收到了一个Terminate-Request报文后,必须回应一个Terminate-Reply报文,同时等待对端A先将链路断开后,再完成本端的所有断开的操作。

    LCP的链路终止报文的数据域与链路配置报文的数据域不一样,链路终止报文中无需携带各配置参数选项。对于链路终止报文也同样需要ID一致,当接收到Terminate-Reply报文才会做链路终止操作。

    Termination request报文:
    在这里插入图片描述
    Termination ACK报文:
    在这里插入图片描述
    3.链路维修包,用于管理和调试一个链路: Code-Reject(代码拒绝), Protocol-Reject(协议拒绝), Echo-Request(回波请求), Echo-Reply(回波应答), 和 Discard-Request(抛弃请求)。

    当接收端发现LCP报文的代码域code是一个不合法的值时,将会向发送端回应一个Code-Reject报文,在回应报文中会将所拒绝报文的全部内容附加上(注:code只有在LCP协议头中才存在)。

    当接收端发现所接收到的PPP数据帧的协议域Protocol是一个不合法的值时,将会向发送端回应一个Protocol-Reject报文,发送端收到该拒绝报文后将停止发送该种协议类型的数据报文了(注:Protocol只有在PPP协议头中才存在)。Protocol-Reject报文只能在LCP的状态机处于Opened状态时才可被处理,而在其它状态接收到该报文将被丢弃。在Protocol-Reject报文的数据域内将携带所拒绝报文的协议类型和报文内容。

    Echo-Request报文和Echo-Reply报文主要用来检测双向链路上自环的问题,除此之外还可附带做一些链路质量的测试和其它功能。当LCP状态机处于Opened状态时,如果接收到了Echo-Request,就需向对端回送一个Echo-Reply报文。否则在其它LCP状态下,该类型的报文会被丢弃。

    Echo-request报文:
    在这里插入图片描述
    Echo-reply报文:
    在这里插入图片描述

    LCP协议具体工作流程:

    场景1:链路协商成功
    在这里插入图片描述
    1.如图所示,R1和R2使用串行链路相连,运行PPP。当物理层链路变为可用状态之后,R1和R2使用LCP协商链路参数。本例中,R1首先发送一个LCP报文。
    2.R1向R2发送Configure-Request报文,此报文包含在发送者(R1)上配置的链路层参数,每个链路层参数使用“类型,长度,取值”的结构表示。
    3.当R2收到此Configure-Request报文之后,如果R2能识别此报文中的所有链路层参数,并且认为每个参数的取值都是可以接受的,则向R1回应一个Configure-Ack报文。
    4.在没有收到Configure-Ack报文的情况下,每隔3秒重传一次Configure-Request报文,如果连续10次发送Configure-Request报文仍然没有收到Configure-Ack报文,则认为对端不可用,停止发送Configure-Request报文。

    注:完成上述过程只是表明R2认为R1上的链路参数配置是可接受的。R2也需要向R1发送Configure-Request报文,使R1检测R2上的链路参数配置是不是可接受的。

    场景2:链路协商参数不成功
    在这里插入图片描述
    1.当R2收到R1发送的Configure-Request报文之后,如果R2能识别此报文中携带的所有链路层参数,但是认为部分或全部参数的取值不能接受,即参数的取值协商不成功,则R2需要向R1回应一个Configure-Nak报文。
    2.在这个Configure-Nak报文中,只包含不能接受的那部分链路层参数列表,每一个包含在此报文中链路层参数的取值均被修改为此报文的发送者(R2)上可以接受的取值(或取值范围)。
    3. 在收到Configure-Nak报文之后,R1需要根据此报文中的链路层参数重新选择本地使用的相关参数,并重新发送一个Configure-Request,序列号需要和Nak报文中的相同。
    4.连续五次协商仍然不成功的参数将被禁用,不再继续协商。

    场景3:链路协商的参数不能被识别
    在这里插入图片描述
    1.当R2收到R1发送的Configure-Request报文之后,如果R2不能识别此报文中携带的部分或全部链路层参数,则R2需要向R1回应一个Configure-Reject报文。
    2.在此Configure-Reject报文中,只包含不被识别的那部分链路层参数列表。
    3.在收到Configure-Reject报文之后,1需要向R2重新发送一个Configure-Request报文,在新的Configure-Request报文中,不再包含不被对端(R2)识别的参数。

    场景4:检测链路状态
    在这里插入图片描述
    1.LCP建立连接之后,可以使用Echo-Request报文和Echo-Reply报文检测链路状态,收到一个Echo-Request报文之后应当回应一个Echo-Reply报文,表示链路状态正常。
    2.VRP平台默认每隔10秒发送一次Echo-Request报文。

    场景5:LCP协议关闭连接
    在这里插入图片描述
    1.认证不成功或者管理员手工关闭等原因可以使LCP关闭已经建立的连接。
    2.LCP关闭连接使用Terminate-Request报文和Terminate-Ack报文,Terminate-Request报文用于请求对端关闭连接,一旦收到一个Terminate-Request报文,LCP必须回应一个Terminate-Ack报文确认连接关闭。
    3.在没有收到Terminate-Ack报文的情况下,每隔3秒重传一次Terminate-Request报文,连续两次重传没有收到Terminate-Ack报文,则认为对端不可用,连接关闭。

    PPP链路防止环路具体流程:
    魔术字在目前所有的设备当中都是需要进行协商的,它被放在Config-Request的配置选项参数中进行发送,而且需要由自身的通信设备独立产生,协议为了避免双方可能产生同样的魔术字,从而导致通信出现不必要的麻烦,因此要求由设备采用一些随机方法产生一个独一无二的魔术字。一般来说魔术字的选择会采用设备的系列号、网络硬件地址或时钟。双方产生相同魔术字的可能性不能说是没有的,但应尽量避免,通常这种情况是发产在相同厂商的设备进行互连时,因为一个厂商所生产的设备产生魔术字的方法是一样的。

    我们知道魔术字产生的作用是用来帮助检测链路是否存在环路,当接收端B收到一个Config-Request报文时,会将此报文与上一次发送出的Config-Request进行比较,如果两个报文中所含的魔术字不一致的话,表明链路不存在环路。但如果一致的话,接收端B认为链路可能存在环路,但不一定存在环路,还需进一步确认。

    此时接收端B将发送一个Config-Nak报文,并在该报文中携带一个重新产生的魔术字,而且此时在未接收到任何Config-Request或Config-Nak报文之前,接收端B也不会发送任何的Config-Request报文。这时我们假设可能会有以下两种情况发生:

    1. 链路实际不存在环路,而是由于对方A在产生魔术字时与接收端B产生的一致,但实际这种情况出现的概率是很小的。当Config-Nak被对端A接收到后,A应该发送一个Config-Request报文(此报文中的魔术字为接收到的Nak报文中的),当B接收到后,与上次的Config-Request比较,由于接收端B已经在上一次的Nak报文中产生了一个不同的魔术字,此时接收端B收到的Config-Request报文中的魔术字与上次B发出的Config-Request配置请求报文中不一样,所以接收端B可断定链路不存在环路。
    2. 链路实际上确实存在环路,一段时间后Config-Nak报文会返回到发送该报文的同一端B。这时接收端B比较这个Config-Nak报文与上一次发出去的Config-Nak报文一样,因此链路存在环路的可能性又增大了。我们知道当一端收到了一个Config-Nak报文时,又会发送一个Config-Request报文(该报文中的魔术字与Config-Nak中的一致),这样又回到了最初的状态,在这条链路上就会不断的出现Config-Request、Config-Nak报文,因此这样周而复始下去,接收端就会认为PPP链路存在环路的可能性在不断增加,当达到一定数量级时,就可认为此链路存在环路。(注意,不是第一次受到相同的魔术字就判断有环路的)

    但在实际应用中根据不同设备实现PPP协议的方法,我们在链路环路检测时可采用两种方法。第一种机制就是如上面所述的,这个过程不断地重复,最终可能会给LCP状态机发一个Down事件,这时可能会使LCP的状态机又回到初始化阶段,又开始新一轮的协商。当然对于某些设备还会采用第二种机制,就是不产生任何事件去影响当前LCP的状态机,而是停留在请求发送状态。但这时认为链路有环路的一端设备需要不断的向链路上发送Echo-Request报文来检测链路环路是否被解除,当接收端收到Echo-Reply报文时,就认为链路环路被解除,从而就可能进行后续的PPP的过程。

    参考资料:华为HCIE培训资料

    展开全文
  • LCP Frames Interpolation Fix

    2020-12-06 10:01:22
    diff --git a/rtengine/lcp.cc b/rtengine/lcp.cc index a1484cdf..d5090dfa 100644 --- a/rtengine/lcp.cc +++ b/rtengine/lcp.cc @@ -390,7 +390,7 @@ void rtengine::LCPProfile...
  • Lcp distortion alt match

    2020-11-28 02:22:55
    <div><p>fixes (well, tries to) some weird problems with some LCP files. more testing for regressions would be appreciated -- I only have 3 lenses with LCP profiles and they work fine, but that doesn&#...
  • LCP Array

    2016-03-10 19:11:44
    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...

    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}s=s1s2...sn, 令\text{suff}_i =s_{i}s_{i+1}...s_{n}suffi=sisi+1...snssii字符开头的后缀. Peter知道任意两个相邻的后缀的最长公共前缀a_i = \text{lcp}(\text{suff}_i, \text{suff}_{i+1}) \quad (1 \le i < nai=lcp(suffi,suffi+1)(1i<n).
    
    现在给你数组aa, Peter有多少个仅包含小写字母的字符串满足这个数组. 答案也许会很大, 你只要输出对10^9 + 7109+7取模的结果即可.
    输入描述
    输入包含多组数据. 第一行有一个整数TT, 表示测试数据的组数. 对于每组数据:
    
    第一行包含一个整数nn (2 \le n \le 10^5)2n105)表示字符串的长度. 第二行包含n - 1n1个整数: a_1,a_2,...,a_{n-1}a1,a2,...,an1 (0 \le a_i \le n)(0ain).
    
    所有数据中nn的和不超过10^6106.
    输出描述
    对于每组数据, 输出答案对10^9+7109+7取模的结果.
    
    输入样例
    3
    3
    0 0
    4
    3 2 1
    3
    1 2
    输出样例
    16250
    26
    0

    这道题的题意不是特别好理解,其实就是说有一个长字符串,然后告诉你每两个相邻字母开始的字符串,从第一个开始连续的有多少个字符是相同的,输入的数肯定不能大于从其开始的字符串的总长度,然后很必要的输入的数必定是严格递减的,一个一个的递减,最后算出这个字符串有多少种可能性。

    #include <iostream>
    #include<cstdio>
    #include<cstring>
    #include<algorithm>
    
    using namespace std;
    #define mm 1000000007
    int main()
    {
        int t,n;
        scanf("%d",&t);
        while(t--)
        {
            long long int ans=26;
            int x[100010];
            memset(x,0,sizeof(x));
            scanf("%d",&n);
            for(int i=1;i<n;i++)
                scanf("%d",&x[i]);
            for(int i=n-1;i>0;i--)
            {
                if(x[i]+1!=x[i-1]&&x[i-1])
                {
                    ans=0;
                    break;
                }
                if(x[i]+i>n)
                {
                    ans=0;
                    break;
                }
                if(!x[i])
                    ans*=25,ans%=mm;
            }
            printf("%I64d\n",ans%mm);
    
        }
        return 0;
    }
    


    展开全文
  • active-set LCP

    2020-11-29 01:05:23
    <div><p>implements an active-set method for LCP time-stepping using the fastQP algorithm <p>resolves #510</p><p>该提问来源于开源项目:RobotLocomotion/drake</p></div>
  • Adds optimize LCP article

    2020-11-28 20:35:28
    <div><p>Fixes #2704 <p>Changes proposed in this pull request: <ul><li>Adds optimize LCP article ⚡ </li></ul>该提问来源于开源项目:GoogleChrome/web.dev</p></div>
  • Readium sdk for lcp

    2020-12-26 07:19:57
    <div><p>I send a pull request for Readium SDK to implement LCP whose target is develop. <p>However it shows "can't automatically merge" message, which had no at the request to the master....
  • LCP 09 BFS

    2020-07-13 23:09:17
    传送门 LCP 09. 最小跳跃次数 题解 观察状态转移,建图并非 DAGDAGDAG,考虑图论。由于只求最小边数,BFSBFSBFS 即可。 class Solution { public: int minJump(vector<int> &jump) { int n = jump.size...
  • <div><p>Leverage the generalized form of LCP input (linear mcp) allowed with pathlcp to reformulate the position constraints with 1/2 of the decision variables. In the first commit, i actually ran ...
  • LCP协商过程

    千次阅读 2017-08-25 09:25:31
    在建立物理层连接后进行LCP协商过程。 LCP协商报文共有4种:  Configure—Request 配置请求,  Configure— ACK 配置准许   Configure—NAK 配置不准许,  Configure—Reject 配置拒绝 设 AB两端进行...
  • LCP 20 DFS

    2020-09-14 16:05:53
    传送门 LCP 20. 快速公交 题解 前向 DFSDFSDFS 状态数显然过多;考虑后向 DFSDFSDFS,从终点搜索至起点。对于某个位置 xxx,有 333 种可能的花费最小的方式到达:直接从起点移动至 xxx;从 x/jump[i]x/jump[i]x/...
  • LCP.1

    2020-02-25 15:54:07
    LETCODE LCP.1猜数字 class Solution { public: int game(vector& guess, vector& answer) { int ret = 0; for (int i = 0; i<guess.size(); i++) { if (guess[i] == answer[i]) { ret++; } ...
  • <div><p>Minor additions to add compatibility with LCP implementations. 1. Expose the property <code>ds:RetrievalMethod</code> in <code>EncryptionInfo</code>. This property is used to detect a LCP ...
  • LCP 19 DP

    2020-09-12 22:13:33
    传送门 LCP 19 题解 dp[i][j]dp[i][j]dp[i][j] 代表字符串分别为连续的 ′r′(j=0)'r'(j=0)′r′(j=0),连续的 ′ry′(j=1)'ry'(j=1)′ry′(j=1),以及连续的 ′ryr′(j=2)'ryr'(j=2)′ryr′(j=2) 所需的最小调整...
  • LCP 操作

    2011-06-20 19:22:07
    LCP 操作包括对链路创建、链路维护和链路切断的策略控制。LCP 操作使用三类 LCP 帧来完成每个 LCP 阶段的工作: Link-establishment 帧负责建立和配置链路(Configure-Request、Configure-Ack、Configure-Nak 和 ...
  • LCP on user interaction?

    2020-11-30 14:37:14
    <div><p>Why is LCP reported on user interaction? <p>I can load my page and sit on it for minutes before clicking, then LCP is reported for those minutes instead of when the actual content is shown. ...
  • LeetCode LCP 17. 速算机器人

    千次阅读 多人点赞 2020-09-14 15:27:39
    LeetCode LCP 17. 速算机器人
  • Linux连接池LCP.zip

    2019-07-19 09:55:42
    LCP是Linux Connection Pool的简写,是基于Linux模块开发的线程安全通用连接池,减少由频繁建立和释放连接带来的系统开销,提升服务响应速度,支持跨语言、多服务的通用连接池,应用层代码不需要做任何改动,对于...
  • LeetCode LCP 06. 拿硬币

    多人点赞 2020-09-07 10:06:46
    LeetCode LCP 06. 拿硬币
  • LCP has lost all linkages

    2020-12-03 00:20:09
    <h3>WP version, LCP plugin version (versions of other software if relevant, e.g. PHP) <p>Wordpress 4.9.8 and LCP 0.79 (If you want to submit a feature request, delete the sections above and describe ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,595
精华内容 1,438
关键字:

LCP