首先先來看第一輪的
假如有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輪增加的高度加上初始高度，就是總共增加的高度
下面是題解寫的過程
?文章來源地址http://www.zghlxwxcb.cn/news/detail-669850.html文章來源：http://www.zghlxwxcb.cn/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';
}
}到了這里，關(guān)于2023 CCPC 華為云計算挑戰(zhàn)賽 D-塔的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
