【Gym-100959H】Random Walk

容斥。

题意:在一个无限大的网格中,一个人从$(0,0)$出发,然后随机走$n$步,每一步等概率地选择上下左右一个方向走一步。求他走过的点数的期望。答案乘$4^n$,模数不是质数。

数据范围:$n<=5000,kcz<=2e9$

我加强了一下,当模数是998244353的时候,可以做到$O(nlogn)$。

做法:

考虑容斥。如果不重复,答案显然为$4^n\ast (n+1)$。注意到,重复经过某一个点,相当于从这个点出发绕一圈又回到该点。并且一个圈(我们要求这个圈内没有其它重复的点)和一次重复是一一对应的。

于是我们枚举圈的长度$i$,对于所有走$n-i$步的$4^{n-i}$种方案,再考虑每种方案上的$n-i+1$个落点,依次从每个点开始绕圈。于是就可以$DP$了。

我们计算长度为$n$有其它重复点的圈的种数,设为$f_n$。则$f_n=\sum_{i=0}^{n/2} \frac {n!}{i!\ast i!\ast (n/2-i)!\ast (n/2-i)}$。

然后没有重复点的$g_n$就是$f_n-\sum_{i=1}^{n-1} f_{n-i}g_i$。

最终答案就是$4^n (n+1)-\sum_i g_i\ast 4^{n-i} (n-i+1)$。

code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
//2019.2.24 by ljz
#include<bits/stdc++.h>
using namespace std;
#define res register LL
#define LL long long
#define inf 0x3f3f3f3f
#define eps 1e-15
inline LL read(){
res s=0;
bool w=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=1;ch=getchar();}
while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
return w?-s:s;
}
inline void _swap(res &x,res &y){
x^=y^=x^=y;
}
inline LL _abs(const res &x){
return x>0?x:-x;
}
inline LL _max(const res &x,const res &y){
return x>y?x:y;
}
inline LL _min(const res &x,const res &y){
return x<y?x:y;
}
const LL N=5e3+10;
namespace MAIN{
LL n,kcz;
inline LL mul(const res &x,const res &y){
return x*y%kcz;
}
inline LL qpow(res x,res y){
res ret=1;
while(y){
if(y&1)ret=mul(ret,x);
y>>=1,x=mul(x,x);
}
return ret;
}
inline void add(res &x,const res &y){
x+=y,x>=kcz?x-=kcz:1,x<0?x+=kcz:1;
}
inline LL Add(const res &x,const res &y){
return x+y>=kcz?x+y-kcz:(x+y<0?x+y+kcz:x+y);
}
LL ans;
LL f[N],g[N];
LL C[N][N];
inline void pre(){
C[0][0]=1;
for(res i=1;i<=n;i++){
C[i][0]=1;
for(res j=1;j<=i;j++)C[i][j]=Add(C[i-1][j],C[i-1][j-1]);
}
}
inline void MAIN(){
n=read(),kcz=read(),pre(),ans=mul(qpow(4,n),n+1);
for(res i=1;i<=n;i++){
if(i&1)continue;
for(res j=0;j<=i/2;j++)add(f[i],mul(C[i/2][j],C[i/2][j]));
f[i]=mul(f[i],C[i][i/2]);
}
for(res i=1;i<=n;i++){
if(i&1)continue;
g[i]=f[i];
for(res j=1;j<=i-1;j++)add(g[i],-mul(f[i-j],g[j]));
add(ans,-mul(g[i],mul(qpow(4,n-i),n-i+1)));
}
printf("%lld\n",ans);
}
}
int main(){
MAIN::MAIN();
return 0;
}

然后看到$f_i$的求法显然是卷积,$g_i$的求法显然可以多项式求逆。所以只要模数好看,显然$O(nlogn)$。