不妨假设$xle y$，可以通过翻转整个格子序列来调整
令$a_{i}$为$i$到$y$的期望步数，显然有方程$a_{i}=egin{cases}0&(i=y)\frac{sum_{j=i+1}^{n}a_{j}}{n-i}+1&(i<y)\frac{sum_{j=1}^{i-1}a_{j}}{i-1}+1&(i>y)end{cases}$
将其写成递推的形式，即
$$
forall 1le ile y-2,a_{i}=frac{n-i-1}{n-i}(a_{i+1}-1)+frac{1}{n-i}a_{i+1}+1=a_{i+1}+frac{1}{n-i}
$$
进一步的，即有$a_{i}=a_{y-1}+sum_{j=i}^{y-2}frac{1}{n-j}$，代入$a_{y+1}$的式子即
$$
a_{y+1}=frac{sum_{i=1}^{y}a_{i}}{y}+1=frac{a_{y-1}+sum_{i=1}^{y-2}(a_{y-1}+sum_{j=i}^{y-2}frac{1}{n-j})}{y}+1=k_{1}a_{y-1}+C_{1}
$$
（其中$k_{1}=frac{y-1}{y},C_{1}=frac{sum_{i=1}^{y-2}sum_{j=i}^{y-2}frac{1}{n-j}}{y}+1$，显然为常数，且不难预处理得到）
类似地，也可以得到$a_{y-1}=frac{n-y}{n-y+1}a_{y+1}+frac{sum_{i=y+2}^{n}sum_{j=y+2}^{i}frac{1}{j-1}}{n-y+1}+1$（同样记为$a_{y-1}=k_{2}a_{y+1}+C_{2}$）
将前者代入后者，即$a_{y-1}=k_{2}(k_{1}a_{y-1}+C_{1})+C_{2}$，解得$a_{y-1}=frac{k_{2}C_{1}+C_{2}}{1-k_{1}k_{2}}$，将$k_{1}$和$k_{2}$的式子代入，不难得到$1-k_{1}k_{2}=frac{n}{y(n-y+1)}$
再根据前面，也即有答案$a_{x}=frac{y(n-y+1)(k_{2}C_{1}+C_{2})}{n}+sum_{i=x}^{y-2}frac{1}{n-i}$（注意特判$x=y$和$y=n$）
综上，$o(n)$预处理后即可$o(1)$计算，时间复杂度为$o(n+T)$
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 2000005 4 #define mod 1000000007 5 #define ll long long 6 int t,n,x,y,ans,inv[N],S1[N],S2[N]; 7 int main(){ 8 inv[0]=inv[1]=S1[0]=S2[0]=1; 9 for(int i=2;i<N;i++)inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod; 10 for(int i=1;i<N;i++)S1[i]=(S1[i-1]+inv[i])%mod; 11 for(int i=1;i<N;i++)S2[i]=(S2[i-1]+S1[i])%mod; 12 scanf("%d",&t); 13 while (t--){ 14 scanf("%d%d%d",&n,&x,&y); 15 if (x>y)x=n-x+1,y=n-y+1; 16 if (x==y){ 17 printf("0 "); 18 continue; 19 } 20 if (y==n){ 21 printf("%d ",(1+S1[n-x]-S1[n-y+1]+mod)%mod); 22 continue; 23 } 24 int k1=(ll)(y-1)*inv[y]%mod,k2=(ll)(n-y)*inv[n-y+1]%mod; 25 int C1=((S2[n-1]-S2[n-y+1]+mod)%mod-(ll)(y-2)*S1[n-y+1]%mod+mod)%mod; 26 int C2=((S2[n-1]-S2[y]+mod)%mod-(ll)(n-y-1)*S1[y]%mod+mod)%mod; 27 C1=((ll)C1*inv[y]+1)%mod,C2=((ll)C2*inv[n-y+1]+1)%mod; 28 ans=(ll)y*(n-y+1)%mod*(((ll)k2*C1+C2)%mod)%mod*inv[n]%mod; 29 ans=(ans+(S1[n-x]-S1[n-y+1]+mod)%mod)%mod; 30 printf("%d ",ans); 31 } 32 return 0; 33 }
View Code