• 周一. 5月 27th, 2024

5G编程聚合网

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

热门标签

[hdu7069]Into the woods

admin

11月 28, 2021

考虑将坐标轴旋转45°,即将$(x,y)$变成$(x+y,x-y)$,显然有$|x|+|y|=max(|x+y|,|x-y|)$

换言之,从新坐标系来看,问题即等价于——初始在$(0,0)$,每一次两维坐标(分别)随机$pm 1$,求$n$次中到原点的切比雪夫距离(即$max(|x|,|y|)$)最大值的期望

令$X$为最远距离,问题即求$E(X)=sum_{i=1}^{n}P(Xge i)=n-sum_{i=1}^{n}P(X<i)$

考虑$P(X<i)$,即要求两维坐标绝对值恒小于$i$,不难发现两维独立且相同(指操作),因此令$p_{i}$为其中一维满足此条件的概率,显然$P(X<i)=p_{i}^{2}$

考虑$p_{i}$的组合意义,即求有多少条从$(0,0)$出发到$(n,j)$($j$为任意$|j|<i$的整数)的路径,其中每一步可以移动到$(x+1,ypm 1)$,且整条路径与$y=pm i$都无交(再将其除以$2^{n}$即为$p_{i}$)

枚举向上的步数$x$,则$j=2x-n$(要求$|j|<i$),并考虑容斥——

总路径数显然为${nchoose x}$,并要减去与两者有交的路径数

定义一条路径的交点序列,为将其与两者的交点依次记录(0表示与$y=i$有交,1表示与$y=-i$有交),并将该序列相同的相邻项合并,得到的01交替出现的序列

令$f(S)$为交点序列存在前缀$S$的路径数,考虑$f(0)+f(1)-f(01)-f(10)+f(010)+f(101)-…$对每一条路径的贡献,对其交点序列的长度奇偶性分类讨论可以发现都为1

换言之,要减去的值即为该式,另外根据对称性其也为$2(f(0)-f(10)+f(010)-f(1010)…)$(这里的对称性其实是指$j$和$-j$时对称)

显然$f(S)$中的$S$由$|S|$决定,不妨枚举$l=|S|$,贡献系数为$2cdot (-1)^{l}$,并考虑此时的$f(S)$

类似于卡特兰数的推导,考虑一条对$f(S)$有贡献的路径,将其第一次与$y=i$交点之前的部分以$y=i$为对称轴翻转,将之后其第一次与$y=-i$交点之前的部分以$y=-i$为对称轴翻转,将之后其第一次与$y=i$交点之前的部分以$y=i$为对称轴翻转……(重复$l$次)

(另外,这是以0为开头的$S$,以1为开头的$S$应该要先取$y=-i$再取$y=i$)

由此,即得到了一条以$(0,2il)$为起点的路径(终点仍为$(n,j)$)

另一方面,对于一条以$(0,2il)$为起点的路径,考虑上述过程的逆过程,不难发现总有交点(注意最后一次以一定是以$y=i$为对称轴翻转),因此同样可以得到一条对$f(S)$有贡献的路径

两者一一对应,因此不妨对后者计数,显然即为${nchoose frac{j-2il+n}{2}}={nchoose x-il}$

综上,路径数为${nchoose x}+2sum_{lge 1}(-1)^{l}{nchoose x-il}$

考虑$x$的范围,由$|j|<i$不难解得为$lfloorfrac{n-i}{2}floor<x<lceilfrac{n+i}{2}ceil$,记$L=lfloorfrac{n-i}{2}floor+1,R=lceilfrac{n+i}{2}ceil-1$,那么即可得到$2^{n}p_{i}=sum_{x=L}^{R}left({nchoose x}+2sum_{lge 1}(-1)^{l}{nchoose x-il}ight)$

将其展开并调换后者的枚举顺序,即$sum_{x=L}^{R}{nchoose x}+2sum_{lge 1}(-1)^{l}sum_{x=L}^{R}{nchoose x-il}$

注意到$x$的枚举都是形如${nchoose i}$的一个区间,可以$o(1)$计算,另外显然有$ille R$的限制,即$l$的范围为$o(frac{n}{i})$,因此直接再在外层枚举$I$,根据调和级数复杂度为$o(nlog n)$

接下来,由最前面的分析,答案即$n-sum_{i=1}^{n}p_{i}^{2}$,直接计算即可

综上,总复杂度为$o(nlog n)$,可以通过

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 1000005
 4 #define ll long long
 5 int t,n,mod,Inv,ans,fac[N],inv[N],sum[N];
 6 int c(int n,int m){
 7     return (ll)fac[n]*inv[m]%mod*inv[n-m]%mod;
 8 }
 9 int main(){
10     scanf("%d",&t);
11     while (t--){
12         scanf("%d%d",&n,&mod);
13         Inv=fac[0]=inv[0]=inv[1]=sum[0]=1,ans=n;
14         for(int i=0;i<n;i++)Inv=(ll)(mod+1)*Inv/2%mod;
15         for(int i=1;i<=n;i++)fac[i]=(ll)fac[i-1]*i%mod;
16         for(int i=2;i<=n;i++)inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
17         for(int i=1;i<=n;i++)inv[i]=(ll)inv[i-1]*inv[i]%mod;
18         for(int i=1;i<=n;i++)sum[i]=(sum[i-1]+c(n,i))%mod;
19         for(int i=1;i<=n;i++){
20             int L=(n-i>>1),R=(n+i-1>>1),s=(sum[R]-sum[L]+mod)%mod;
21             for(int l=1;i*l<=R;l++){
22                 int ss=sum[R-i*l];
23                 if (L-i*l>=0)ss=(ss-sum[L-i*l]+mod)%mod;
24                 ss=2*ss%mod;
25                 if (l&1)s=(s-ss+mod)%mod;
26                 else s=(s+ss)%mod;
27             }
28             s=(ll)s*Inv%mod;
29             ans=(ans-(ll)s*s%mod+mod)%mod;
30         }
31         printf("%d
",ans);
32     }
33     return 0;
34 }

View Code

《[hdu7069]Into the woods》有2个想法

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注