【SSL 1458】zzzyyds（DP）

zzzyyds

题目链接：SSL 1458

题目大意

有一个环，一开始全白，每次随机选一个点染黑，如果存在一个白色点两边都是黑色点那它会变成黑色，然后每次染了之后判定白色的数量，如果小于等于 k 就结束，否则分数增加，增加量为黑色点个数的 t 次方。
问你最后期望分数。

思路

首先我们考虑假设一定要它选到白色的，因为这样不会向自身转移。

那我们先化简式子：（假设 $j$ 个位置是白色的，一次的费用是 $Q$）
$f_a=\frac{j}{d}{f}_b+\frac{d-j}{d}{f}_a+Q$
$\frac{j}{d}{f}_a=\frac{j}{d}{f}_b+Q$
$f_a=f_b+\frac{d}{j}Q$

然后我们就只用看转移到别人，思考有哪些分类情况。
发现状态还是难以表示，于是考虑把一些状态归成一类。
发现我们可以把黑色的点弄成若干段，那其实有不同的是白色点的个数。
那我们设 $f_{i,j}$ 为白色点有 $i$ 个，黑色点分成了 $j$ 段。

那考虑所有的情况，然后段之间一定要分开，所以你考虑一段带上右边的白色点，然后再插到剩下的白色点里面去。
然后因为你是环，你要确定 $1$ 的位置，所以两个位置都要减一。
也就是 $\left(\genfrac{}{}{0ex}{}{i-j-1}{j-1}\right)$，我们设其为 $w(i,j)$

然后进行情况讨论：

1. 所有的情况：$w(i,j)\ast i$（这里是算上你选的情况）
2. 放在了一个长度只有 $2$ 的白色段之间：$w(i-2,j-1)\ast 2j$（相当于你把这个白色的段插入到 $(i-2,j-1)$ 的情况中，多了两个变色，黑色也裂多了一个段，然后你这个白色段你可以选左边或者右边的变黑）
3. 放在了一个长度为 $3$ 的白色段的中间：$w(i-3,j-1)\ast j$（跟上一个道理，不用乘二是因为只能选中间的染黑）
4. 放在了黑色段的旁边：$w(i-1,j)\ast 2j$（也是黑色段的两边都可以，然后占掉了一个变色）
5. 放在了黑色段隔一个的旁边：$w(i-2,j)\ast 2j$（跟上面同一个道理）
6. 放在中间把一个白色段变成两半，这个的数量可以用所有减去前面的特别情况得到，然后转移呢是到 $i-1,j+1$。
   （前面的转移是跟 $w$ 里面的位置一样的）

然后记得是期望，概率，所以要除所有的情况（$1$）。
然后最后直接枚举 $f$，按我们一开始推出的式子贡献如答案即可。

代码

#include
#define mo 998244353
#define ll long long

using namespace std;

const int N = 2005;
int d, k, t;
ll f[N][N], jc[N], inv[N], invs[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;
}

ll C(int i, int j) {
	if (i < 0) return 0;
	if (j < 0 || j > i) return 0;
	return jc[i] * invs[j] % mo * invs[i - j] % mo;
}

ll way(int i, int j) {
	if (!i && !j) return 1;
	return C(i - j - 1, j - 1);
}
//"-j"要隔位置 1...10 一块，"-1" 是环固定一个确定起点

int main() {
	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;
	invs[0] = 1; for (int i = 1; i < N; i++) invs[i] = invs[i - 1] * inv[i] % mo;
	
	scanf("%d %d %d", &d, &k, &t);
	f[d - 1][1] = 1;
	for (int i = d - 1; i > 1; i--)
		for (int j = 1; j <= d; j++) {
			if (!f[i][j] || !way(i, j)) continue;
			ll tot = way(i, j) * i % mo, now, di = f[i][j] * ksm(tot, mo - 2) % mo;
			now = way(i - 2, j - 1) * 2 * j % mo; if (now) (f[i - 2][j - 1] += now * di % mo) %= mo; (tot += mo - now) %= mo;
			now = way(i - 3, j - 1) * j % mo; if (now) (f[i - 3][j - 1] += now * di % mo) %= mo; (tot += mo - now) %= mo;
			now = way(i - 1, j) * 2 * j % mo; if (now) (f[i - 1][j] += now * di % mo) %= mo; (tot += mo - now) %= mo;
			now = way(i - 2, j) * 2 * j % mo; if (now) (f[i - 2][j] += now * di % mo) %= mo; (tot += mo - now) %= mo;
			if (tot) (f[i - 1][j + 1] += tot * di % mo) %= mo;
		}
	
	ll ans = 0;
	for (int i = k + 1; i <= d - 1; i++)
		for (int j = 1; j <= d; j++)
			(ans += f[i][j] * d % mo * inv[i] % mo * ksm(d - i, t) % mo) %= mo;
	printf("%lld", ans);
	
	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