牛客41668B 灵魂之火 II

标签：41668B 打出 int 张牌 II 牛客 include define

你有n张牌，其中m张牌可以打出并且随机弃掉一张牌，这m张牌如果能出一定会打出，其他牌均不可打出，问期望能出多少张牌

考虑期望dp，有 \(i\) 张牌其中 \(j\) 张牌可以打出的期望为 \(f_{i,j}\)，转移方程为

\[f_{i,j} = f_{i - 2, j - 2} * \frac{j - 1}{i - 1} + f_{i - 2, j - 1} * \frac{i - j}{i - 1} + 1 \]

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

#define file(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout);
#define dbg(x) cerr<<"In Line"<<__LINE__<<" the "<<#x<<" = "<<x<<'\n';
#define abs(x) ((x) < 0 ? -(x) : (x))

using namespace std;

const int N = 2e6 + 10, mod = 1e9 + 7;

inline int read() {
	bool sym = 0; int res = 0; char ch = getchar();
	while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
	while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
	return sym ? -res : res;
}

int n, m, k, f[2050][2050], inv[N];

int qpow(int a, int x) {
	int res = 1;
	while (x) {if (x & 1) res = 1ll * res * a % mod; a = 1ll * a * a % mod; x >>= 1;}
	return res;
}

int main() {
	int T = read(); n = 2022; inv[1] = 1;
	for (int i = 2; i <= n; i++) inv[i] = qpow(i, mod - 2);
	for (int i = 1; i <= n; i++) {
		f[i][1] = 1; f[i][2] = 1ll * ((i - 2 << 1) + 1) * inv[i - 1] % mod;
		for (int j = 3; j <= i; j++) {
			f[i][j] = (1ll * f[i - 2][j - 2] * (j - 1) + 1ll * f[i - 2][j - 1] * (i - j) + i - 1) % mod * inv[i - 1] % mod;
		}
	}
	while (T--) {
		n = read(); m = read(); printf("%d\n", (1ll * f[n][m] << 2) % mod);
	}
	return 0;
}

标签：41668B,打出,int,张牌,II,牛客,include,define
From： https://www.cnblogs.com/zrzring/p/NC41668B.html