UOJ#211. 【UER #6】逃跑（Dynamic Programming）题意题解CODE

93 阅读 0 评论 62 点赞

我是靠谱客的博主拉长水壶，这篇文章主要介绍UOJ#211. 【UER #6】逃跑（Dynamic Programming）题意题解CODE，现在分享给大家，希望可以做个参考。

题意

????

简要版： 在一个二维平面上走 $n$ 步，每次随机往上下左右四个方向走 $1$ 单位长度，四个方向的概率权重分别为 $w_1,w_2,w_3,w_4$ 。设 $W=w_1+w_2+w_3+w_4$ ，即四个方向的概率分别是 $frac{w_1}{W},frac{w_2}{W},frac{w_3}{W},frac{w_4}{W}$ 。

设这 $n$ 步内（包括起点）到达的不同位置个数的方差为 $V/W^n$ ，求 $W^n$ 对 $998244353$ 取模后的值。

解释版： 在一个二维平面上走 $n$ 步，每次随机走 $1$ 单位长度，上下左右四个方向分别有 $w_1,w_2,w_3,w_4$ 种走法，每一步总共 $W=w_1+w_2+w_3+w_4$ 种走法。

令随机变量 $x$ 为这 $n$ 步内经过的不同的位置数， $E (X)$ 为随机变量 $X$ 的期望，且

$V=Eleft((x-E(x))^2right)times W^n$

求 $Vtimes(w_1+w_2+w_3+w_4)^n$ 对 $998244353$ 取模后的值。

数据范围

$w_1,w_2,w_3,w_4leq100,1leq W$ 。

题解

预告：本题解只需定义并使用 3 个动态规划数组

首先来化这个式子 $Eleft((x-E(x))^2right)$

我们把它展开：
$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)$

因此，我们要分别求两个东西：不同位置数的期望和不同位置数的平方的期望。

求位置数的期望，先求所有方案的不同位置数之和，再除去总方案数。

首先我们需要一个最基本的工具数组： $w a n [i] [x] [y]$ ，表示任意走 $i$ 步从 $(0, 0)$ 到 $(x, y)$ 的方案数，转移很简单，为了节约空间我就不写了。

我们让每个位置在第一次到达的时候做出 $1$ 的贡献，那么可以通过统计每一步是否到达新位置，具体地，令 $g [i]$ 为走了 $i$ 步，第 $i$ 步到达一个新位置的方案数，那么所有方案的不同位置数之和就是
$S_1=sum_{i=0}^n g(i)cdot W^{n-i}$

而 $g [i]$ 的转移可以通过全集减去不合法方案得到，不合法方案就是最后若干步形成一个圈，走回来了：
$g[i]=W^i-sum_{j=0}^{i-1}g[j]cdot wan[i-j][0][0]\ g[0]=1$

然后求位置数的平方的期望。

我们知道 $x^2=2{xchoose 2}+x$ ，所以 $E(x^2)=2E({xchoose 2})+E(x)$ ，我们实际上需要求 $E ((2 x))$ ，问题转化为求经过的不同位置之间配对的方案数。对于某一种行走方案，在经过的位置之间任选两个的方案数，可以等价为在经过的 $n + 1$ 个位置中任选两个第一次出现的位置。具体地可以统计每个位置第一次出现后有多少位置第一次出现，然后求和。

最朴素的定义法是令 $f [i] [x] [y] [a] [b]$ 表示走 $i$ 步第一次到达 $(x, y)$ 、途径 $(a, b)$ （说明在 $(a, b)$ 第一次出现后）的方案数，但是状态数太多了，必须砍两维。为了方便转移，我们令 $F[i][x][y]=sum_{a,b}f[i][a+x][b+y][a][b]$ ，直接对 $F [i] [x] [y]$ 进行转移和使用。

我们可以枚举 $(a, b)$ 第一次经过的时间，算出一个粗略的方案数
$F[i][x][y]=Big(sum_{j=0}^{i-1}g[j]cdot wan[i-j][x][y]Big)-...$

这种方案保证了 $(a, b)$ 是在 $j$ 时刻第一次到达的，但是 $(a + x, b + y)$ 却不一定是在第 $i$ 步第一次到达，它产生了两种不合法方案：「 $(a + x, b + y)$ 第一次到达的步数 $< j$ 」、「 $(a + x, b + y)$ 第一次到达的步数 $\in (j, i)$ 」。我们需要分别把它们减去。

若 $(a + x, b + y)$ 第一次到达的步数 $< j$ ，说明 $(a, b)$ 和 $(a + x, b + y)$ 的地位颠倒了，而且最后又走回了 $(a + x, b + y)$ ，所以可以通过 $F [k] [- x] [- y]$ 转移过来，即 $(a, b), (a + x, b + y)$ 变成了 $(a^{'} - x, b^{'} - y), (a^{'}, b^{'})$ ：
$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)-...$

若 $(a + x, b + y)$ 第一次到达的步数 $\in (j, i)$ ，说明原本在 $k (k < i)$ 步的时候就到了 $(a + x, b + y)$ （此时方案数 $F [k] [x] [y]$ ），然后绕圈，混到第 $i$ 步重回 $(a + x, b + 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) - Big(sum_{k=1}^{i-1}F[k][x][y]cdot wan[i-k][0][0]Big)$

于是，我们要求的不同位置之间配对的方案数 $\sum (2 x)$ 即为
$S_2=sum_{i,x,y}F[i][x][y]cdot W^{n-i}$

最终输出的就是
$(2S_2+S_1)cdot W^n-S_1^2$

时间复杂度 $O(n^4)$ ，转移剪一剪枝，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;
}

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#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;
}