OI - Borrow(HDU) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - Borrow(HDU)

发表于 分类于 Valine：

好得没话说的题

# 题面

点击展开/折叠 题面

三个人玩游戏，一开始每个人分别有 $x,y,z$ 枚硬币。每轮游戏，有最多硬币的人（如果有两个人的硬币数量最多，则随机选取一人）把自己的一枚硬币随机地给另外两个人之一。游戏一直进行到三个人有一样多的硬币。

给定 $x,y,z$，求游戏期望进行多少轮，或期望值为 $+\infty$ 输出 $-1$。

# 解析

记 $n=x+y+z$，不难想到一个状态数为 $n^2$ 的 DP；为了方便下面分析正解，这里采取一个（在之后的正解中）更为优美的 DP 定义：$f(a,b)$ 表示，当最大值与另外两个值之差分别为 $a,b$ 时，期望进行多少轮结束。

为了方便描述，令 $a=x-y,b=x-z$，即 $x$ 为最大值。

终止状态 $f(0,0)=0$，不可达状态为 $3\not\mid a+b$ 的 $f(a,b)$。

然后考虑转移，需要注意的是转移硬币后最大值改变的情况：

  • 若 $a,b\ge 2$，则 $x$ 无论分给哪一个，$x$ 也一定还是最大值，则有 $f(a,b)=\frac{f(a-1,b-2)+f(a-2,b-1)}2+1$；

  • 若 $a=1,b\ge 2$（$b=1,a\ge 2$ 同理）：

    如果 $x$ 分给 $z$，则 $x-1=y\ge z+1$，最大值不变：$f(0,b-2)$；

    如果分给 $y$，则 $y+1=x,x-1=y$，其实并没有变化：$f(1,b)$；

    则有 $f(1,b)=\frac{f(0,b-2)+f(1,b)}2+1$；

  • 若 $a=0,b\ge 2$：

    如果 $x$ 分给 $y$，则最大值变为 $y+1$，新的状态为 $f(2,b+1)$；

    如果 $x$ 分给 $z$，则最大值变为 $y$，新的状态为 $f(1,b-1)$；

    则有 $f(0,b)=\frac{f(2,b+1)+f(1,b-1)}2+1$；

对于 $f(0,b)$ 的转移式，把 $f(2,b+1)$ 的转移式代入可得：

这样我们消元得到了一个无环的 DP，可以在时间复杂度 $O(n^2)$ 内求解。

进一步分析，DP的转移只有在 $a<2$ 或 $b<2$ 时是需要消元来解环的，其他时候（$a,b\ge 2$）的转移形式都是“日字形”，从 $(a,b)$ 转到 $(a-1,b-2)/(a-2,b-1)$。

那么可以先 $O(n)$ 预处理出 $f(0/1,b)$，然后直接计算每个 $f(0/1,b)$ 对 $f(x,y)$ 的贡献——

  • $f(1,b)$ 对 $f(x,y)$ 的贡献就是 $T(L+f(1,b))\times2^L$，其中 $T$ 是从 $(x,y)$ 走日字形走到 $(1,b)$ 的路径条数，路径长度为 $L$。
  • $f(0,b)$ 的贡献仍然是 $T(L+f(1,b))\times2^L$，但是注意 $T$ 包含的路径不能经过 $f(1,b+2)$，不然会和 $f(1,b+2)$ 的贡献算重。

# 源代码

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<cassert>
#include<algorithm>
using namespace std;

const int MOD=998244353,N=1e6+10;
#define ci const int &

inline int Add(ci a,ci b){return a+b>=MOD? a+b-MOD:a+b;}
inline int Sub(ci a,ci b){return a-b<0? a-b+MOD:a-b;}
inline int Mul(ci a,ci b){return int(1ll*a*b%MOD);}
inline int Pow(ci a,ci b){return b? Mul(Pow(Mul(a,a),b>>1),(b&1)? a:1):1;}

const int INV2=Pow(2,MOD-2);

int f[N][2],fac[N<<1],ifac[N<<1],ivpow[N<<1];

void InitDP(){
	f[0][0]=0;
	for(int x=2;x<N;x++){
		if((x+1)%3==0) f[x][1]=Add(f[x-2][0],2);
		if(x%3==0) f[x][0]=Add(f[x-1][1],2);
//		if(x<=10) printf("%d : %d\n",x,f[x][0]);
	}
	fac[0]=1;
	for(int i=1;i<(N<<1);i++) fac[i]=Mul(fac[i-1],i);
	ifac[(N<<1)-1]=Pow(fac[(N<<1)-1],MOD-2);
	for(int i=(N<<1)-2;i>=0;i--) ifac[i]=Mul(ifac[i+1],i+1);
	ivpow[0]=1;
	for(int i=1;i<(N<<1);i++) ivpow[i]=Mul(ivpow[i-1],INV2);
}
void Sort(int &x,int &y,int &z){
	if(x<y) swap(x,y);
	if(x<z) swap(x,z);
	if(y<z) swap(y,z);
}
inline int Comb(int b,int a){return a>b? 0:Mul(fac[b],Mul(ifac[a],ifac[b-a]));}
inline int DP(int x,int y){
	int ret=0;
	//(x,y) -> (1,i)
	for(int i=2;i<=y;i++){
		int dx=x-1,dy=y-i;
		if((dx+dy)%3) continue;
		int p=(2*dx-dy)/3,q=(2*dy-dx)/3;
		if(p<0 || q<0) continue;
		assert(p+q<(N<<1));
		ret=Add(ret,Mul(Mul(ivpow[p+q],Comb(p+q,p)),p+q+f[i][1]));
	}
	//(x,y) -> (0,i)
	for(int i=2;i<=y;i++){
		int dx=x-0,dy=y-i;
		if((dx+dy)%3) continue;
		int p=(2*dx-dy)/3,q=(2*dy-dx)/3;
		if(p<0 || q<0) continue;
		assert(p+q<(N<<1));
		ret=Add(ret,Mul(Mul(ivpow[p+q],Comb(p+q,p)),p+q+f[i][0]));
		ret=Sub(ret,Mul(Mul(ivpow[p+q],Comb(p+q-1,p)),p+q+f[i][0]));
	}
	return ret;
}
int main(){
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	InitDP();
	int cas;
	scanf("%d",&cas);
	while(cas--){
		int a,b,c;scanf("%d%d%d",&a,&b,&c);
		int n=a+b+c;
		if(n%3){printf("-1\n");continue;}
		Sort(a,b,c);
		int x=a-b,y=a-c;
		if(x<y) swap(x,y);
		if(y<2){printf("%d\n",f[x][y]);continue;}
		printf("%d\n",Add(DP(x,y),DP(y,x)));
	}
	return 0;
}

THE END

Thanks for reading!

> Linked 赤途-网易云