思路
先不考虑重叠情况
n
u
m
[
i
]
num[i]
num[i]为
n
e
x
t
[
i
]
next[i]
next[i]递归的次数，不可能递归，优化为递推递推，每个点取上一个唯一
p
o
s
pos
pos，模型为
D
A
G
DAG
DAG，其实也是一棵树
考虑不重叠情况
对于每个i,我只需要找到
<
=
i
2
<= \frac{i}2
<=2i 的祖先
f
a
t
,
n
u
m
[
f
a
t
]
fat,num[fat]
fat,num[fat] 的数量满足情况的
a
n
s
[
p
o
s
]
ans[pos]
ans[pos] ，倍增预处理，再倍增缩小范围。
题目链接
#pragma GCC optimize(2)
#pragma GCC target ("sse4")
#include<bits/stdc++.h>
#define ull unsigned long long
#define F first
#define S second
#define endl "\n"
#define eps 1e-6
#define base 131
#define lowbit(x) (x&(-x))
#define db double
#define PI acos(-1.0)
#define inf 0x3f3f3f3f
#define MAXN 0x7fffffff
#define INF 0x3f3f3f3f3f3f3f3f
#define _for(i, x, y) for (int i = x; i <= y; i++)
#define for_(i, x, y) for (int i = x; i >= y; i--)
#define ferma(a,b) pow(a,b-2)
#define mod(x) (x%mod+mod)%mod
#define pb push_back
#define decimal(x) cout << fixed << setprecision(x);
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define memset(a,b) memset(a,b,sizeof(a));
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std
;
#ifndef ONLINE_JUDGE
#include "local.h"
#endif
template<typename T
> inline T
fetch(){T ret
;cin
>> ret
;return ret
;}
template<typename T
> inline vector
<T
> fetch_vec(int sz
){vector
<T
> ret(sz
);for(auto& it
: ret
)cin
>> it
;return ret
;}
template<typename T
> inline void makeUnique(vector
<T
>& v
){sort(v
.begin(), v
.end());v
.erase(unique(v
.begin(), v
.end()), v
.end());}
template<typename T
> inline T
max_(T a
,T b
){if(a
>b
)return a
;return b
;}
template<typename T
> inline T
min_(T a
,T b
){if(a
<b
)return a
;return b
;}
void file()
{
#ifdef ONLINE_JUDGE
#else
freopen("D:/LSNU/codeforces/duipai/data.txt","r",stdin);
freopen("D:/LSNU/codeforces/duipai/WA.txt","w",stdout);
#endif
}
void Match()
{
#ifdef ONLINE_JUDGE
#else
Debug
::Compare();
#endif
}
const int N
=1e6+5;
const int mod
=1e9+7;
int Next
[N
],dp
[21][N
],num
[N
];
char str
[N
];
signed main()
{
file();
int t
;
scanf("%d",&t
);
while(t
--)
{
scanf("%s",str
);
int n
=strlen(str
);
Next
[0]=-1;
int j
=0,k
=-1;
while(j
<n
)
{
if(k
==-1||str
[j
]==str
[k
])
++j
,++k
,Next
[j
]=k
,dp
[0][j
]=k
;
else
k
=Next
[k
];
}
for(int i
=1;i
<=n
;++i
)
num
[i
]=1ll*(num
[Next
[i
]]+1)%mod
;
for(int i
=1;i
<=20;++i
)
for(int j
=1;j
<=n
;++j
)
dp
[i
][j
]=dp
[i
-1][dp
[i
-1][j
]];
int ans
=1;
for(int i
=1;i
<=n
;++i
)
{
int pos
=i
;
for(int j
=20;j
>=0;--j
)
if(dp
[j
][pos
]>i
/2)
pos
=dp
[j
][pos
];
ans
=1ll*ans
*(1+num
[dp
[0][pos
]])%mod
;
}
printf("%d\n",ans
);
}
Match();
return 0;
}
