题面
题解
后缀数组当然可以
这里用哈希做
首先排序的问题在哪里
在于比较两个后缀的复杂度是O(length)的
但是我们可以通过找LCP来优化比较
我们二分两个串的LCP的长度 然后通过hash值判断是否相同
这样我们可以在$O(\log l)$的时间内算出两个串的LCP长度
所以排序的复杂度变成$O(n \log ^2 n )$
然后求出连续两个后缀的LCP还是用二分的方法做 复杂度$O(n \log n)$
总的复杂度$O(n \log ^2 n)$
Code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; ll read(){
ll x=,f=;char c=getchar();
while(c<'' || c>''){if(c=='-')f=-;c=getchar();}
while(c>='' && c<=''){x=x*+c-'';c=getchar();}
return x*f;
} const int maxn=;
const int mod=1e9+;
int mu[maxn],pr[maxn],cnt;
bool isp[maxn];
int fib[maxn],g[maxn],G[maxn],invG[maxn];
int fpw[maxn][]; inline int ksm(int a,int b){
int ret=;
for(int i=;i<=;i++){
if(b&) ret=ret*1ll*a%mod;
a=a*1ll*a%mod;
b=b>>;
if(b==) return ret;
}
} inline int inv(int a){
return ksm(a,mod-);
} int main(){
#ifdef LZT
freopen("in","r",stdin);
#endif
mu[]=;
memset(isp,,sizeof(isp));
for(int i=;i<=;i++){
if(isp[i]){
pr[++cnt]=i;
mu[i]=-;
}
for(int j=;j<=cnt && i*pr[j]<=;j++){
isp[i*pr[j]]=;
if(i%pr[j]==) break;
mu[i*pr[j]]=-mu[i];
}
} fib[]=;
for(int i=;i<=;i++)
fib[i]=(fib[i-]+fib[i-])%mod;
for(int i=;i<=;i++){
fpw[i][]=inv(fib[i]);
fpw[i][]=;
fpw[i][]=fib[i];
}
for(int i=;i<=;i++)
g[i]=;
for(int i=;i<=;i++)
for(int j=i;j<=;j+=i)
g[j]=g[j]*1ll*fpw[i][mu[j/i]+]%mod;
G[]=;
for(int i=;i<=;i++)
G[i]=G[i-]*1ll*g[i]%mod; invG[]=;
for(int i=;i<=;i++)
invG[i]=inv(G[i]); int tc=read();
while(tc--){
int n=read(),m=read();
int j;
int ans=;
for(int i=;i<=min(n,m);i=j+){
j=min(n/(n/i),m/(m/i));
ans=ans*1ll*ksm(G[j]*1ll*invG[i-]%mod,(n/i)*1ll*(m/i)%(mod-))%mod;
}
printf("%d\n",ans);
} return ;
}