[hdu7000]二分

不妨假设$x\le y$，可以通过翻转整个格子序列来调整

令$a_{i}$为$i$到$y$的期望步数，显然有方程$a_{i}=\begin{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 1\le i\le 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\n");

18             continue;

19         }

20         if (y==n){

21             printf("%d\n",(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\n",ans);

31     }

32     return 0;

33 }

巴特西

[hdu7000]二分

最新文章

热门文章