概述
题意
????
简要版： 在一个二维平面上走 n n n 步，每次随机往上下左右四个方向走 1 1 1 单位长度，四个方向的概率权重分别为 w 1 , w 2 , w 3 , w 4 w_1,w_2,w_3,w_4 w1,w2,w3,w4。设 W = w 1 + w 2 + w 3 + w 4 W=w_1+w_2+w_3+w_4 W=w1+w2+w3+w4 ，即四个方向的概率分别是 w 1 W , w 2 W , w 3 W , w 4 W frac{w_1}{W},frac{w_2}{W},frac{w_3}{W},frac{w_4}{W} Ww1,Ww2,Ww3,Ww4 。
设这 n n n 步内（包括起点）到达的不同位置个数的方差为 V / W n V/W^n V/Wn，求 V × W n Vtimes W^n V×Wn 对 998244353 998244353 998244353 取模后的值。
解释版： 在一个二维平面上走 n n n 步，每次随机走 1 1 1 单位长度，上下左右四个方向分别有 w 1 , w 2 , w 3 , w 4 w_1,w_2,w_3,w_4 w1,w2,w3,w4 种走法，每一步总共 W = w 1 + w 2 + w 3 + w 4 W=w_1+w_2+w_3+w_4 W=w1+w2+w3+w4 种走法。
令随机变量 x x x 为这 n n n 步内经过的不同的位置数， E ( X ) E(X) E(X) 为随机变量 X X X 的期望，且
V = E ( ( x − E ( x ) ) 2 ) × W n V=Eleft((x-E(x))^2right)times W^n V=E((x−E(x))2)×Wn
求 V × ( w 1 + w 2 + w 3 + w 4 ) n Vtimes(w_1+w_2+w_3+w_4)^n V×(w1+w2+w3+w4)n 对 998244353 998244353 998244353 取模后的值。
数据范围
1 ≤ n ≤ 100 , 0 ≤ w 1 , w 2 , w 3 , w 4 ≤ 100 , 1 ≤ W 1leq nleq100,0leq w_1,w_2,w_3,w_4leq100,1leq W 1≤n≤100,0≤w1,w2,w3,w4≤100,1≤W 。
题解
预告：本题解只需定义并使用 3 个动态规划数组
首先来化这个式子 E ( ( x − E ( x ) ) 2 ) Eleft((x-E(x))^2right) E((x−E(x))2)
我们把它展开：
E
(
(
x
−
E
(
x
)
)
2
)
=
E
(
x
2
+
E
2
(
x
)
−
2
E
(
x
)
x
)
=
E
(
x
2
)
+
E
(
E
2
(
x
)
)
−
E
(
2
E
(
x
)
x
)
=
E
(
x
2
)
+
E
2
(
x
)
−
2
E
(
x
)
E
(
x
)
=
E
(
x
2
)
−
E
2
(
x
)
Eleft((x-E(x))^2right)=Eleft(x^2+E^2(x)-2E(x)xright)\ =E(x^2)+E(E^2(x))-E(2E(x)x)=E(x^2)+E^2(x)-2E(x)E(x)\ ~\ =E(x^2)-E^2(x)
E((x−E(x))2)=E(x2+E2(x)−2E(x)x)=E(x2)+E(E2(x))−E(2E(x)x)=E(x2)+E2(x)−2E(x)E(x) =E(x2)−E2(x)
因此，我们要分别求两个东西：不同位置数的期望 和 不同位置数的平方的期望 。
求位置数的期望，先求所有方案的不同位置数之和，再除去总方案数。
首先我们需要一个最基本的工具数组： w a n [ i ] [ x ] [ y ] wan[i][x][y] wan[i][x][y] ，表示任意走 i i i 步从 ( 0 , 0 ) (0,0) (0,0) 到 ( x , y ) (x,y) (x,y) 的方案数，转移很简单，为了节约空间我就不写了。
我们让每个位置在第一次到达的时候做出
1
1
1 的贡献，那么可以通过统计每一步是否到达新位置，具体地，令
g
[
i
]
g[i]
g[i] 为走了
i
i
i 步，第
i
i
i 步到达一个新位置的方案数，那么所有方案的不同位置数之和就是
S
1
=
∑
i
=
0
n
g
(
i
)
⋅
W
n
−
i
S_1=sum_{i=0}^n g(i)cdot W^{n-i}
S1=i=0∑ng(i)⋅Wn−i
而
g
[
i
]
g[i]
g[i] 的转移可以通过全集减去不合法方案得到，不合法方案就是最后若干步形成一个圈，走回来了：
g
[
i
]
=
W
i
−
∑
j
=
0
i
−
1
g
[
j
]
⋅
w
a
n
[
i
−
j
]
[
0
]
[
0
]
g
[
0
]
=
1
g[i]=W^i-sum_{j=0}^{i-1}g[j]cdot wan[i-j][0][0]\ g[0]=1
g[i]=Wi−j=0∑i−1g[j]⋅wan[i−j][0][0]g[0]=1
然后求位置数的平方的期望。
我们知道 x 2 = 2 ( x 2 ) + x x^2=2{xchoose 2}+x x2=2(2x)+x，所以 E ( x 2 ) = 2 E ( ( x 2 ) ) + E ( x ) E(x^2)=2E({xchoose 2})+E(x) E(x2)=2E((2x))+E(x)，我们实际上需要求 E ( ( x 2 ) ) E({xchoose2}) E((2x)) ，问题转化为求经过的不同位置之间配对的方案数。对于某一种行走方案，在经过的位置之间任选两个的方案数，可以等价为在经过的 n + 1 n+1 n+1 个位置中任选两个第一次出现的位置。具体地可以统计每个位置第一次出现后有多少位置第一次出现，然后求和。
最朴素的定义法是令 f [ i ] [ x ] [ y ] [ a ] [ b ] f[i][x][y][a][b] f[i][x][y][a][b] 表示走 i i i 步第一次到达 ( x , y ) (x,y) (x,y) 、途径 ( a , b ) (a,b) (a,b) （说明在 ( a , b ) (a,b) (a,b) 第一次出现后）的方案数，但是状态数太多了，必须砍两维。为了方便转移，我们令 F [ i ] [ x ] [ y ] = ∑ a , b f [ i ] [ a + x ] [ b + y ] [ a ] [ b ] F[i][x][y]=sum_{a,b}f[i][a+x][b+y][a][b] F[i][x][y]=∑a,bf[i][a+x][b+y][a][b] ，直接对 F [ i ] [ x ] [ y ] F[i][x][y] F[i][x][y] 进行转移和使用。
我们可以枚举
(
a
,
b
)
(a,b)
(a,b) 第一次经过的时间，算出一个粗略的方案数
F
[
i
]
[
x
]
[
y
]
=
(
∑
j
=
0
i
−
1
g
[
j
]
⋅
w
a
n
[
i
−
j
]
[
x
]
[
y
]
)
−
.
.
.
F[i][x][y]=Big(sum_{j=0}^{i-1}g[j]cdot wan[i-j][x][y]Big)-...
F[i][x][y]=(j=0∑i−1g[j]⋅wan[i−j][x][y])−...
这种方案保证了 ( a , b ) (a,b) (a,b) 是在 j j j 时刻第一次到达的，但是 ( a + x , b + y ) (a+x,b+y) (a+x,b+y) 却不一定是在第 i i i 步第一次到达，它产生了两种不合法方案：「 ( a + x , b + y ) (a+x,b+y) (a+x,b+y) 第一次到达的步数 < j <j <j」 、「 ( a + x , b + y ) (a+x,b+y) (a+x,b+y) 第一次到达的步数 ∈ ( j , i ) in(j,i) ∈(j,i)」。我们需要分别把它们减去。
若
(
a
+
x
,
b
+
y
)
(a+x,b+y)
(a+x,b+y) 第一次到达的步数
<
j
<j
<j ，说明
(
a
,
b
)
(a,b)
(a,b) 和
(
a
+
x
,
b
+
y
)
(a+x,b+y)
(a+x,b+y) 的地位颠倒了，而且最后又走回了
(
a
+
x
,
b
+
y
)
(a+x,b+y)
(a+x,b+y) ，所以可以通过
F
[
k
]
[
−
x
]
[
−
y
]
F[k][-x][-y]
F[k][−x][−y] 转移过来，即
(
a
,
b
)
,
(
a
+
x
,
b
+
y
)
(a,b),(a+x,b+y)
(a,b),(a+x,b+y) 变成了
(
a
′
−
x
,
b
′
−
y
)
,
(
a
′
,
b
′
)
(a'-x,b'-y),(a',b')
(a′−x,b′−y),(a′,b′) ：
F
[
i
]
[
x
]
[
y
]
=
(
∑
j
=
0
i
−
1
g
[
j
]
⋅
w
a
n
[
i
−
j
]
[
x
]
[
y
]
)
−
(
∑
k
=
1
i
−
1
F
[
k
]
[
−
x
]
[
−
y
]
⋅
w
a
n
[
i
−
k
]
[
x
]
[
y
]
)
−
.
.
.
F[i][x][y]=Big(sum_{j=0}^{i-1}g[j]cdot wan[i-j][x][y]Big) - Big( sum_{k=1}^{i-1}F[k][-x][-y]cdot wan[i-k][x][y] Big)-...
F[i][x][y]=(j=0∑i−1g[j]⋅wan[i−j][x][y])−(k=1∑i−1F[k][−x][−y]⋅wan[i−k][x][y])−...
若
(
a
+
x
,
b
+
y
)
(a+x,b+y)
(a+x,b+y) 第一次到达的步数
∈
(
j
,
i
)
in(j,i)
∈(j,i) ，说明原本在
k
(
k
<
i
)
k(k<i)
k(k<i) 步的时候就到了
(
a
+
x
,
b
+
y
)
(a+x,b+y)
(a+x,b+y) （此时方案数
F
[
k
]
[
x
]
[
y
]
F[k][x][y]
F[k][x][y]），然后绕圈，混到第
i
i
i 步重回
(
a
+
x
,
b
+
y
)
(a+x,b+y)
(a+x,b+y) ：
F
[
i
]
[
x
]
[
y
]
=
(
∑
j
=
0
i
−
1
g
[
j
]
⋅
w
a
n
[
i
−
j
]
[
x
]
[
y
]
)
−
(
∑
k
=
1
i
−
1
F
[
k
]
[
−
x
]
[
−
y
]
⋅
w
a
n
[
i
−
k
]
[
x
]
[
y
]
)
−
(
∑
k
=
1
i
−
1
F
[
k
]
[
x
]
[
y
]
⋅
w
a
n
[
i
−
k
]
[
0
]
[
0
]
)
F[i][x][y]=Big(sum_{j=0}^{i-1}g[j]cdot wan[i-j][x][y]Big) - Big( sum_{k=1}^{i-1}F[k][-x][-y]cdot wan[i-k][x][y] Big) - Big(sum_{k=1}^{i-1}F[k][x][y]cdot wan[i-k][0][0]Big)
F[i][x][y]=(j=0∑i−1g[j]⋅wan[i−j][x][y])−(k=1∑i−1F[k][−x][−y]⋅wan[i−k][x][y])−(k=1∑i−1F[k][x][y]⋅wan[i−k][0][0])
于是，我们要求的不同位置之间配对的方案数
∑
(
x
2
)
sum{xchoose2}
∑(2x) 即为
S
2
=
∑
i
,
x
,
y
F
[
i
]
[
x
]
[
y
]
⋅
W
n
−
i
S_2=sum_{i,x,y}F[i][x][y]cdot W^{n-i}
S2=i,x,y∑F[i][x][y]⋅Wn−i
最终输出的就是
(
2
S
2
+
S
1
)
⋅
W
n
−
S
1
2
(2S_2+S_1)cdot W^n-S_1^2
(2S2+S1)⋅Wn−S12
时间复杂度 O ( n 4 ) O(n^4) O(n4) ，转移剪一剪枝，3 秒内通过不难。
CODE
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<stack>
#include<random>
#include<vector>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 105
#define LL long long
#define ULL unsigned long long
#define DB double
#define lowbit(x) (-(x) & (x))
#define ENDL putchar('n')
#define FI first
#define SE second
LL read() {
LL f=1,x=0;int s = getchar();
while(s < '0' || s > '9') {if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
while(s >= '0' && s <= '9') {x = (x<<3) + (x<<1) + (s^48); s = getchar();}
return f*x;
}
void putpos(LL x) {if(!x)return ;putpos(x/10);putchar('0'+(x%10));}
void putnum(LL x) {
if(!x) {putchar('0');return ;}
if(x<0) {putchar('-');x = -x;}
return putpos(x);
}
void AIput(LL x,int c) {putnum(x);putchar(c);}
const int MOD = 998244353;
int n,m,s,o,k;
int qkpow(int a,int b) {
int res = 1;
while(b > 0) {
if(b & 1) res = res *1ll* a % MOD;
a = a*1ll*a % MOD; b >>= 1;
}return res;
}
const int MX = 103;
int Abs(int x) {return x<0 ? -x:x;}
int wan[MAXN][MAXN<<1][MAXN<<1];
int g[MAXN],po[MAXN];
int F[MAXN][MAXN<<1][MAXN<<1];
int w1,w2,w3,w4;// (1,0) (-1,0) (0,1) (0,-1)
int e1,e2;
int dis(int x,int y) {return Abs(x) + Abs(y);}
int main() {
n = read();
w1 = read(); w2 = read(); w3 = read(); w4 = read();
int W = w1+w2+w3+w4;
po[0] = 1;
for(int i = 1;i <= n;i ++) po[i] = po[i-1] *1ll* W % MOD;
int invl = qkpow(po[n],MOD-2);
wan[0][MX][MX] = 1;
for(int t = 1;t <= n;t ++) {
for(int i = -t;i <= t;i ++) {
int ab = t - Abs(i);
for(int j = -ab;j <= ab;j ++) {
wan[t][i+MX][j+MX] = (
wan[t-1][MX+i-1][MX+j] *1ll* w1 % MOD +
wan[t-1][MX+i+1][MX+j] *1ll* w2 % MOD +
wan[t-1][MX+i][MX+j-1] *1ll* w3 % MOD +
wan[t-1][MX+i][MX+j+1] *1ll* w4 % MOD) % MOD;
}
}
}
g[0] = 1;
e1 = po[n];
for(int t = 1;t <= n;t ++) {
g[t] = po[t];
for(int j = 1;j <= t;j ++) {
(g[t] += MOD - wan[j][MX][MX] *1ll* g[t-j] % MOD) %= MOD;
}
(e1 += g[t]*1ll*po[n-t] % MOD) %= MOD;
}
for(int t = 1;t <= n;t ++) {
for(int i = -t;i <= t;i ++) {
int ab = t - Abs(i);
for(int j = -ab;j <= ab;j ++) {
int d = dis(i,j);
if(d) {
for(int k = 0;k <= t-d;k ++) {
(F[t][MX+i][MX+j] += g[k] *1ll* wan[t-k][MX+i][MX+j] % MOD) %= MOD;
(F[t][MX+i][MX+j] += MOD - F[k][MX-i][MX-j] *1ll* wan[t-k][MX+i][MX+j] % MOD) %= MOD;
}
for(int k = d;k < t;k ++) {
(F[t][MX+i][MX+j] += MOD - F[k][MX+i][MX+j] *1ll* wan[t-k][MX][MX] % MOD) %= MOD;
}
(e2 += F[t][MX+i][MX+j] *1ll* po[n-t] % MOD) %= MOD;
}
}
}
}
e2 = (e2 * 2ll + e1) % MOD;
e1 = e1 *1ll* e1 % MOD * invl % MOD;
printf("%d %dn",e2,e1);
int ans = (e2 +MOD- e1) % MOD *1ll* po[n] % MOD;
AIput(ans,'n');
return 0;
}
最后
以上就是拉长水壶为你收集整理的UOJ#211. 【UER #6】逃跑 （Dynamic Programming）题意题解CODE的全部内容，希望文章能够帮你解决UOJ#211. 【UER #6】逃跑 （Dynamic Programming）题意题解CODE所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复