考虑将坐标轴旋转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