2023 CCPC 华为云计算挑战赛 D-塔-Toy模板网

这篇具有很好参考价值的文章主要介绍了2023 CCPC 华为云计算挑战赛 D-塔。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

首先先来看第一轮的
假如有n个,每轮那k个

他们的高度的可能性分别为

n 1/C(n,k)

n+1 C(n-(k-1+1),1)/C(n,k)

n+2 C(n-(k-2+1),2)/C(n,k)

n+i C(n-(k-i+1,i)/C(n,k)

通过概率和高度算出第一轮增加的期望

然后乘上m轮增加的高度加上初始高度，就是总共增加的高度

下面是题解写的过程

2023 CCPC 华为云计算挑战赛 D-塔,华为云

文章来源地址https://www.toymoban.com/news/detail-669850.html

const int inf = 0x3f3f3f3f3f3f3f3f, N = 2e5 + 5, mod = 998244353;
int qpow(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) res = res * a % mod;
		b >>= 1;
		a = a * a % mod;
	}
	return res;
}
int fpow(int x, int r) {
	int result = 1;
	while (r) {
		if (r & 1)result = result * x % mod;
		r >>= 1;
		x = x * x % mod;
	}
	return result;
}

namespace binom {
	int fac[N], ifac[N];
	int __ = [] {
		fac[0] = 1;
		for (int i = 1; i <= N - 5; i++)
			fac[i] = fac[i - 1] * i % mod;
		ifac[N - 5] = fpow(fac[N - 5], mod - 2);
		for (int i = N - 5; i; i--)
			ifac[i - 1] = ifac[i] * i % mod;
		return 0;
	}();

	inline int C(int n, int m) {
		if (n < m || m < 0)return 0;
		return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
	}

	inline int A(int n, int m) {
		if (n < m || m < 0)return 0;
		return fac[n] * ifac[n - m] % mod;
	}
}
using namespace binom;//求解排列组合
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n, m, k;
		cin >> n >> m >> k;
		int fen = qpow(C(n, k), mod - 2);
		int ans = 0;
//		cout << C(3, 3) << '\n';
		ans = (ans + n * fen) % mod;
		for (int i = 1; i <= k; i++) {
//			cout << "------\n" << n - (k - i)-1 << ' ' << (k-i) << "\n" << "---------\n";
//			cout << C(n - (k - i) - 1, i) << '\n';
			ans = (ans + ((n+i) * fen) % mod * C(n - (k - i+1), i) % mod) % mod;
		}
		int w = (ans - n + mod) % mod;
		cout << (n + w * m % mod) % mod << '\n';
	}
}

到了这里，关于2023 CCPC 华为云计算挑战赛 D-塔的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！