Smiling & Weeping

　　　　　　　　　　　　　　　　---- 你是我的，半截的诗，不许别人更改一个字

题目链接：P2375 [NOI2014] 动物园 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路详解：这道题目是要求解：有多少个我现在希望求出一个更强大

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int mode = 1000000007;
 5 int n , Next[1000100] , slen;
 6 int nxt[1000100] , num[1000100];
 7 ll ans;
 8 char str[1000100];
 9 void getnext(char *s , int slen){
10     int p=0 , k=1,l;
11     nxt[0] = slen;
12     while(p+1 < slen && s[p]==s[p+1]) p++;
13     nxt[1] = p;
14     for(int i = 2; i < slen; i++){
15         p = k+nxt[k]-1;
16         l = nxt[i-k];
17         if(i+l <= p) nxt[i] = l;
18         else {
19             int j = max(0 , p-i+1);
20             while(i+j < slen && s[i+j] == s[j]) j++;
21             nxt[i] = j;
22             k = i;
23         }
24     }
25 }
26 void solve(){
27     for(int i = 1; i < slen; i++){
28         if(str[i] == str[0]){
29             int len = min(i , nxt[i]);
30             // 会被卡，TLE，改用前缀和，可以通过
31             // for(int j = i; j <= i+len-1; j++)
32             //     num[i]++;
33             num[i]++; num[i+len]--;
34         }
35     }
36     for(int i = 1; i < slen; i++)
37         num[i] += num[i-1];
38 }
39 int main()
40 {
41     scanf("%d",&n);
42     while(n--){
43         ans = 1;
44         scanf("%s",str);
45         slen = strlen(str);
46         getnext(str , slen);
47         solve();
48         for(int i = 1; i < slen; i++)
49             ans = ans*(num[i]+1)%mode , num[i] = 0;
50         printf("%lld",ans);
51         if(n) printf("\n");
52     }
53     return 0;
54 }

不要因为也许会改变，就不肯说那句美丽的誓言；

不要因为也许会分离，就不敢求一次倾心的相遇；

文章到此结束，我们下次再见跳舞(((((ી(･◡･)ʃ)))))

JZTXT

动物园

Smiling & Weeping