题解 P2375 【[NOI2014]动物园】

神TM阅读理解题 看完题目之后 暴力：每次暴跳$next$数组 太慢啦 优化一下暴力： 搞个倍增数组来跳$next$ 每次倍增跳$next$ 复杂度$O(Tnlogn)$ 算一下，感觉复杂度差不多呀 很果断的交了一发 然后$80$分。。。 暴力代码送上： ```cpp #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<set> #include<map> #include<vector> #include<queue> using namespace std; #define MOD 1000000007 char s[1200000]; int nt[1200000]; int jp[1200000][21]; int main() { int T; scanf("%d",&T); while(T--) { scanf("%s",s+1); nt[1]=0; int l=strlen(s+1); for(int i=2;i<=l;++i) { int j=nt[i-1]; while(j&&s[i]!=s[j+1])j=nt[j]; if(s[i]==s[j+1])nt[i]=j+1; else nt[i]=0; jp[i][0]=nt[i]; } for(int j=1;j<20;++j) for(int i=1;i<=l;++i) jp[i][j]=jp[jp[i][j-1]][j-1]; int ans=1; for(int i=2;i<=l;++i) { int tt=i; for(int j=19;j>=0;--j) if(jp[tt][j]*2>i)tt=jp[tt][j]; int gg=0; for(int j=19;j>=0;--j) if(jp[tt][j])gg+=1<<j,tt=jp[tt][j]; ans=1ll*ans*(gg+1)%MOD; } printf("%d\n",ans); } return 0; } ``` --- 然后我很不爽 把倍增数组的两维反了过来，防止反复横跳 然后我就$AC$了？？？ ~~又一次感受到玄学强大的力量~~ 这个$O(Tnlogn)$的复杂度果然很对呀。。。 暴力能AC？？？： （BZOJ上都能AC？？？） ```cpp #include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<algorithm> #include<set> #include<map> #include<vector> #include<queue> using namespace std; #define MOD 1000000007 char s[1200000]; int nt[1200000]; int jp[21][1200000]; int main() { int T; scanf("%d",&T); while(T--) { scanf("%s",s+1); nt[1]=0; int l=strlen(s+1); for(int i=2;i<=l;++i) { int j=nt[i-1]; while(j&&s[i]!=s[j+1])j=nt[j]; if(s[i]==s[j+1])nt[i]=j+1; else nt[i]=0; jp[0][i]=nt[i]; } for(int j=1;j<20;++j) for(int i=1;i<=l;++i) jp[j][i]=jp[j-1][jp[j-1][i]]; int ans=1; for(int i=2;i<=l;++i) { int tt=i; for(int j=19;j>=0;--j) if(jp[j][tt]*2>i)tt=jp[j][tt]; int gg=0; for(int j=19;j>=0;--j) if(jp[j][tt])gg+=1<<j,tt=jp[j][tt]; ans=1ll*ans*(gg+1)%MOD; } printf("%d\n",ans); } return 0; } ``` ~~我的复杂度还是太弱了~~ ~~这是一篇来自蒟蒻的题解~~