C/C++教程

【AGC056E】Cheese(DP)

本文主要是介绍【AGC056E】Cheese(DP),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Cheese

题目链接:AGC056E

题目大意

给你一个环,边上有老鼠,然后会进行 n-1 次操作:
每次选一个一个点放一个奶酪(每个点的概率给出),然后奶酪会顺时针跑,每到一个老鼠就判定是否被吃,被吃了就那个老鼠和这个奶酪都没了。
要你求最后剩下某个老鼠的概率。

思路

首先做这个东西有一个很重要的点:
就是到时什么东西的顺序是有关系的。

你会发现这个奶酪的顺序没有太大的关系,最后用一个重排把类型乘起来就就可以了。
那我们就可以再让所有的奶酪先走到同一个位置(把放下的提前放下),然后再处理一直转圈的情况。

那一开始的东西我们考虑用 DP 求:
\(f_{i,j,k}\) 表示现在到 \(i\) 点,放了 \(j\) 个奶酪,已经有 \(k\) 个被吃了的情况。
然后你就根据两个东西转移:放奶酪和奶酪被吃。
放奶酪不难看,枚举在一个位置放这个奶酪的概率,然后在这个转移的时候不要忘记把重排的下面部分也乘上。
接着是看吃奶酪。
那我们就看这个位置吃不吃,怎么看概率呢,如果吃了就是这当前还在的 \(j\) 个里面有一个吃了,概率是 \(\dfrac{1}{2^j}\),那没吃自然就是 \(1-\dfrac{1}{2^j}\)。

然后接着考虑怎么转圈。
考虑对于 \(x\) 个奶酪在两个在剩下的 \(y\) 个老鼠中跑,考虑位置相邻的老鼠 \(i,i+1\),它们两个谁会留下来。
如果都挂了或者都没有挂(就只看一轮),那都没有意义。
如果 \(i\) 挂了 \(i+1\) 没挂,那概率是 \((1-\dfrac{1}{2^x})\dfrac{1}{2^{x-1}}\)
如果 \(i+1\) 挂了 \(i\) 没挂,那概率是 \(\dfrac{1}{2^x}(1-\dfrac{1} {2^x})\)

然后你看看他们两个的比例,会发现是 \(2:1\)!
也就是说 \(p_i:p_{i+1}=1:2\)(\(p_i\) 是 \(i\) 留下来的概率)
那显然 \(\sum\limits_{i=1}^np_i=1\),所以就是有 \(p_i=\dfrac{2^{i-1}}{2^n-1}\)
那我们要的是第一个,所以就是 \(\dfrac{1}{2^n-1}\)。

然后用 DP 的 \(f_{n,n-1,x}\) 来搞,这里对应的就是 \(n-x\) 个老鼠的答案。
然后就好了。

代码

#include<cstdio>
#include<cstring>
#define ll long long
#define mo 998244353

using namespace std;

const int N = 40 + 5;
int n;
ll a[N], jc[N], inv[N], two[N], twv[N], f[N][N][N];

ll ksm(ll x, ll y) {
	ll re = 1;
	while (y) {
		if (y & 1) re = re * x % mo;
		x = x * x % mo; y >>= 1;
	}
	return re;
}

void Init() {
	jc[0] = 1; for (int i = 1; i < N; i++) jc[i] = jc[i - 1] * i % mo;
	inv[0] = inv[1] = 1; for (int i = 2; i < N; i++) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
	for (int i = 1; i < N; i++) inv[i] = inv[i - 1] * inv[i] % mo;
	two[0] = 1; for (int i = 1; i < N; i++) two[i] = two[i - 1] * 2 % mo;
	ll tmp = ksm(2, mo - 2); twv[0] = 1; for (int i = 1; i < N; i++) twv[i] = twv[i - 1] * tmp % mo;
}

int main() {
	Init();
	
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%lld", &a[i]); a[i] = a[i] * ksm(100, mo - 2) % mo;
	}
	
	for (int x = 0; x < n; x++) {
		memset(f, 0, sizeof(f)); f[0][0][0] = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j < n; j++)
				for (int k = 0; k <= j; k++) {
					for (ll l = 0, g = 1; l <= j - k; l++, g = g * a[(x + i) % n] % mo) {
						(f[i][j][k] += f[i - 1][j - l][k] * g % mo * inv[l] % mo) %= mo;
					}
				}
			if (i != n) {
				for (int j = 0; j < n; j++) {
					for (int k = j; k >= 0; k--) {
						if (k != j) (f[i][j][k + 1] += f[i][j][k] * (1 - twv[j - k] + mo) % mo) %= mo;
						(f[i][j][k] *= twv[j - k]) %= mo;
					}
				}
			}
			else {
				ll ans = 0;
				for (int j = 1; j <= n; j++) {
					(ans += f[n][n - 1][n - j] * jc[n - 1] % mo * ksm((two[j] - 1 + mo) % mo, mo - 2) % mo) %= mo;
				}
				printf("%lld ", ans);
			}
		}
	}
	
	return 0;
}
这篇关于【AGC056E】Cheese(DP)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!