• 周六. 7月 2nd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[hdu7000]二分

admin

11月 28, 2021

不妨假设$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

发表评论

您的电子邮箱地址不会被公开。